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.

Pages: 1 2

4 Responses to “List Swap”

  1. Jussi Piitulainen said

    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)))
    
  2. matthew said

    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"𝀃𝀄𝀅𝀆𝀇𝀈𝀉"); 	
    }
    
    $ ./a.out
    ⲀⲂⲄⲆⲈⲊ
    ⲊⲂⲄⲆⲈⲀ
    ⲊⲈⲄⲆⲂⲀ
    ⲊⲈⲆⲄⲂⲀ
    ⲊⲈⲄⲆⲂⲀ
    ⲊⲂⲄⲆⲈⲀ
    ⲀⲂⲄⲆⲈⲊ
    𝀃𝀄𝀅𝀆𝀇𝀈𝀉
    𝀉𝀄𝀅𝀆𝀇𝀈𝀃
    𝀉𝀈𝀅𝀆𝀇𝀄𝀃
    𝀉𝀈𝀇𝀆𝀅𝀄𝀃
    𝀉𝀈𝀇𝀆𝀅𝀄𝀃
    𝀉𝀈𝀅𝀆𝀇𝀄𝀃
    𝀉𝀄𝀅𝀆𝀇𝀈𝀃
    𝀃𝀄𝀅𝀆𝀇𝀈𝀉
    
  3. kernelbob said

    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 }

  4. matthew said

    @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"☿♀♁♂♃♄♅♆♇");
    }
    
    ①②③④⑤⑥
    ⑥②③④⑤①
    ⑥⑤③④②①
    ⑥⑤④③②①
    ⑥⑤③④②①
    ⑥②③④⑤①
    ①②③④⑤⑥
    ☿♀♁♂♃♄♅♆♇
    ♇♀♁♂♃♄♅♆☿
    ♇♆♁♂♃♄♅♀☿
    ♇♆♅♂♃♄♁♀☿
    ♇♆♅♄♃♂♁♀☿
    ♇♆♅♄♃♂♁♀☿
    ♇♆♅♂♃♄♁♀☿
    ♇♆♁♂♃♄♅♀☿
    ♇♀♁♂♃♄♅♆☿
    ☿♀♁♂♃♄♅♆♇
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: