Swapping Elements

Given the parameter “target”, in order to swap a node with it’s adjacent sibling (target + 1):

int i = 0;
node* prev = NULL;
node* walk = head;

if ( target == 0)
  return // We'll explain this later

while ( i < target ) {
  if walk != NULL {
    prev = walk;
    walk = walk->next;

prev->next = walk->next;
walk->next = walk->next->next
prev->next->next = walk;

let target = 1

walk represents our target node, and prev refers to the last target node assigned at each iteration of our while loop.

As our counter iterates, we “walk” our list forward, keeping track of the last node passed on the way until we’ve reached our target index.

Here is where we swap:

Have our previous element “skip over” the target element

prev->next = walk->next;

Have our target element “skip over” the adjacent element

walk->next = walk->next->next;

Finally, point our adjacent element at the target element

prev->next->next = walk;

Try to ignore the prev references, and you’ll see the swap operation was successful, yet leaves those prev references intact.

Now if focus is placed on the prev references…

It is now trivial to finish the swap operation

prev->next->prev = prev;

walk->next->prev = walk;

walk->prev = prev->next;