## 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;
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;
};

// 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;
}
node **const pp0 = pp;      // k elements from beginning
node **pp1 = &list;
node *half = list;
bool escapement = false;
while (true) {
if (*pp == NULL) {
break;
}
if (half == *pp)
return NULL;        // cyclic list
if (escapement)
escapement = !escapement;
}

// Exchange *pp0 and *pp1.
node *p0 = *pp0;
node *p1 = *pp1;
*pp1 = p0;
*pp0 = p1;

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;
}

{
printf("{ ");
int i = 0;
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(p->value == i + 1 == k ? n - k + 1 : i == n - k ? k : i + 1);
}

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