Swap alternate nodes in a singly linked list - Algorithms and Problem SolvingAlgorithms and Problem Solving

Swap alternate nodes in a singly linked list - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a single Linked List. Swap every other alternate nodes.

For example, given 1–>2–>3–>4–>5–>null then output 3–>4–>5–>2–>1–>null. Note that, the list was transformed in several steps.

1. First step, swap 1 and 3 i.e. 3–>2–>1–>4–>5–>null
2. Second step, swap 2 and 4 i.e. 3–>4–>1–>2–>5–>null
3. last step, swap 1 and 5, i.e. 3–>4–>5–>2–>1–>null

We can observe that, each step it is reversing the linked list of size 3 from current node and moving the head to next node for next step. Reversing a 3 element linked list is pretty simple using two swaps (or using 2 temp variables). The hardest part of this problem is to maintain the head of the list. Here is a simple but working code.

public static LinkedListNode swapAlternateNodes(final LinkedListNode head) {      if (head == null || head.next == null) {          return head;      }        LinkedListNode newhead = null;      LinkedListNode prev = head;      LinkedListNode cur = prev.next;      LinkedListNode temp = null;      LinkedListNode lastTemp = null;      while (cur != null && cur.next != null) {          temp = cur.next;            prev.next = cur.next.next;          cur.next = prev;          temp.next = cur;            if (newhead == null) {              newhead = temp;          } else {              lastTemp.next = temp;          }            prev = cur;          cur = cur.next;          lastTemp = temp;      }        return newhead;  }  

 

Sometimes this problem is confused with another problem of swapping alternate pair of elements which will transform 1–>2–>3–>4–>5–>null into 2–>1–>4–>3–>5–>null. This one is pretty simple as we are swapping 2 elements each step.

Read full article from Swap alternate nodes in a singly linked list - Algorithms and Problem SolvingAlgorithms and Problem Solving