List Swap
December 13, 2016
We have today an exercise for students who work with linked lists:
Given a linked list and an integer k, swap the two list items that are at distance k from the beginning of the list and distance k from the end of the list. Be sure to consider the case where the k cross, so that the item k from the beginning of the list is after the item k from the end of the list. For instance, given the list (1 2 3 4 5 6 7) and k = 2, you should return the list (1 6 3 4 5 2 7), and likewise if k = 6. The solution must run in O(n) time, where n is the length of the list.
Your task is to write the list-swapping code described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
This does up to five O(n) scans, which is still O(n), and works (without special consideration) when an item is swapped with itself or when the position from the beginning is further in the list than the position from the end, and (accidentally) even when both positions are outside the list. The auxiliaries use 0-based indexing. The solution is 1-based as in the spec.
(define (swap xs j k) (define (help xs j k) (lambda (a o) (cond ((= a j) (list-ref xs k)) ((= a k) (list-ref xs j)) (else o)))) (map/index (help xs j k) xs)) (define (map/index proc xs) (let loop ((k 0) (xs xs) (rs '())) (if (null? xs) (reverse rs) (loop (+ k 1) (cdr xs) (cons (proc k (car xs)) rs))))) (define (solution xs k) (swap xs (- k 1) (- (length xs) k)))It’s not difficult to do the swaps in place:
#include <locale.h> #include <iostream> #include <algorithm> struct Cons { Cons(wchar_t v, Cons *n) : value(v), next(n) {} wchar_t value; Cons *next; }; void swap(Cons *&root, int n) { // Create a pointer to the root Cons **p = &root; // Advance it n times for (int i = 0; i < n; i++) { p = &(*p)->next; // Return without change if list too short if (*p == 0) return; } // Now *p points at the first pointer cell to // be swapped. // q is another pointer to the root, r is the // list after the first n items, so the distance // between *q and r is n. Cons **q = &root, *r = *p; // Advance them in step until r gets to the end. while(true) { r = r->next; if (r == 0) break; q = &(*q)->next; } // Now *q points at the second pointer cell to be // swapped, so swap the pointers to the cells: std::swap(*p,*q); // and swap the rest pointers of the swapped cells: std::swap((*p)->next,(*q)->next); } void test(const wchar_t *s) { Cons *root = 0; int N = wcslen(s); for (int i = N; i > 0; i--) { root = new Cons(s[i-1],root); } for (int i = 0; i <= N; i++) { for (Cons *p = root; bool(p); p = p->next) { std::wcout << p->value; } std::wcout << "\n"; swap(root,i); } } int main() { setlocale (LC_ALL, ""); test(L"ⲀⲂⲄⲆⲈⲊ"); test(L"𝀃𝀄𝀅𝀆𝀇𝀈𝀉"); }It looks like my C solution is pretty similar to Matthew’s C++. There’s really only one way to do it in the C family…
However, mine does detect cyclic lists and returns NULL for those.
#include <assert.h> #include <stdbool.h> #include <stddef.h> #include <stdio.h> typedef struct node node; struct node { int value; node *link; }; // Modify a linked list in place, exchanging the k'th elements from // the beginning and end of the list. // // The given example shows that k is one-based: the list starts with // item 1, not item 0. // // Returns the new head of list. // Returns NULL if list is shorter than k elements or is cyclic. node *list_swap(node *list, unsigned k) { if (!k) return NULL; // EINVAL node **pp = &list; node **npp = pp; for (unsigned i = 0; i < k; i++) { if (!*npp) return NULL; // fewer than k elements. pp = npp; npp = &(*pp)->link; } node **const pp0 = pp; // k elements from beginning node **pp1 = &list; node *half = list; bool escapement = false; while (true) { pp = &(*pp)->link; if (*pp == NULL) { break; } pp1 = &(*pp1)->link; if (half == *pp) return NULL; // cyclic list if (escapement) half = half->link; escapement = !escapement; } // Exchange *pp0 and *pp1. node *p0 = *pp0; node *p1 = *pp1; *pp1 = p0; *pp0 = p1; node *p0link = p0->link; p0->link = p1->link; p1->link = p0link; return list; } node *init_list(node arena[], size_t n) { for (int i = 0; i < n; i++) { arena[i].value = i + 1; arena[i].link = (i < n - 1) ? &arena[i + 1] : NULL; } return n ? arena : NULL; } void check_answer(node *head, node arena[], unsigned k, size_t n) { printf("{ "); int i = 0; for (node *p = head; p; p = p->link) { if (++i > 20) { printf("... "); break; } printf("%d ", p->value); } printf("}\n"); #define SWIZ(i) (((i) + 1 == k) ? n - k : ((i) == n - k) ? k - 1 : i) for (size_t i = 0; i < n; i++) { size_t ip1 = SWIZ(i + 1); node *p = &arena[SWIZ(i)]; node *next = (ip1 < n) ? &arena[ip1] : NULL; if (i == 0) assert(head == p); assert(p->value == i + 1 == k ? n - k + 1 : i == n - k ? k : i + 1); assert(p->link == next); } #undef SWIZ } int main() { node arena[7]; // List lengths 0-7, 1 <= k <= n for (size_t n = 0; n <= 7; n++) { for (unsigned k = 1; k <= n; k++) { node *list = init_list(arena, n); node *l0 = list_swap(list, k); check_answer(l0, arena, k, n); } // Short list node *list = init_list(arena, n); assert(list_swap(list, n + 1) == NULL); } // Circular lists for (size_t i = 0; i < 7; i++) { for (unsigned k = 1; k <= 7; k++) { node *list = init_list(arena, 7); arena[6].link = &arena[i]; assert(list_swap(list, k) == NULL); } } return 0; }Running it.
$ cc list-swap.c && a.out
{ 1 }
{ 2 1 }
{ 2 1 }
{ 3 2 1 }
{ 1 2 3 }
{ 3 2 1 }
{ 4 2 3 1 }
{ 1 3 2 4 }
{ 1 3 2 4 }
{ 4 2 3 1 }
{ 5 2 3 4 1 }
{ 1 4 3 2 5 }
{ 1 2 3 4 5 }
{ 1 4 3 2 5 }
{ 5 2 3 4 1 }
{ 6 2 3 4 5 1 }
{ 1 5 3 4 2 6 }
{ 1 2 4 3 5 6 }
{ 1 2 4 3 5 6 }
{ 1 5 3 4 2 6 }
{ 6 2 3 4 5 1 }
{ 7 2 3 4 5 6 1 }
{ 1 6 3 4 5 2 7 }
{ 1 2 5 4 3 6 7 }
{ 1 2 3 4 5 6 7 }
{ 1 2 5 4 3 6 7 }
{ 1 6 3 4 5 2 7 }
{ 7 2 3 4 5 6 1 }
@kernelbob: Pleased to be in good company. NIce point about circular lists. Here’s a version that should fix that (I don’t address the problem of freeing circular structures though). I’ve unrolled the loop once rather than use a flag variable:
#include <locale.h> #include <assert.h> #include <iostream> #include <algorithm> struct Cons { Cons(wchar_t v, Cons *n) : value(v), next(n) {} wchar_t value; Cons *next; }; bool swap(Cons *&root, int n) { // Create a pointer to the root Cons **p = &root; // Advance it n times for (int i = 0; i < n; i++) { p = &(*p)->next; // Return without change if list too short if (*p == 0) return false; } // Now *p points at the first pointer cell to // be swapped. // q is another pointer to the root, r is the // list after the first n items, so the distance // between *q and r is n. Cons **q = &root, *r = *p, *s = r; // Advance them in step until r gets to the end. while (true) { r = r->next; if (r == s) return false; if (r == 0) break; q = &(*q)->next; r = r->next; if (r == s) return false; if (r == 0) break; q = &(*q)->next; s = s->next; } // Now *q points at the second pointer cell to be // swapped, so swap the pointers to the cells: std::swap(*p,*q); // and swap the rest pointers of the swapped cells: std::swap((*p)->next,(*q)->next); return true; } void test(const wchar_t *s) { Cons *root = 0; int N = wcslen(s); for (int i = N; i > 0; i--) { root = new Cons(s[i-1],root); } for (int i = 0; ; i++) { for (Cons *p = root; bool(p); p = p->next) { std::wcout << p->value; } std::wcout << "\n"; if (!swap(root,i)) break; } Cons *last = root; while (last->next) last = last->next; for (int i = 0; i < N; i++) { Cons *p = root; for (int j = 0; j < i; j++) p = p->next; last->next = p; assert(!swap(root,2*N)); } } int main() { setlocale (LC_ALL, ""); test(L"①②③④⑤⑥"); test(L"☿♀♁♂♃♄♅♆♇"); }