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.
- First step, swap 1 and 3 i.e. 3–>2–>1–>4–>5–>null
- Second step, swap 2 and 4 i.e. 3–>4–>1–>2–>5–>null
- 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.
ublic static LinkedListNode swapPairNodes(LinkedListNode head) { if (head == null || head.next == null) { return head; } LinkedListNode newHead = null; LinkedListNode cur = head; LinkedListNode prev = null; LinkedListNode temp = null; while (cur != null && cur.next != null) { temp = cur.next; cur.next = cur.next.next; temp.next = cur; if (prev != null) { prev.next = temp; } if (newHead == null) { newHead = temp; } prev = cur; cur = cur.next; } head = newHead; return newHead; }
Bonus Question: Delete List Nodes With Larger Value Node On Right
Given a single linked list. Delete all the elements that has lager value element on right of it.
public static ListNode deleteNodeWithHighOnRight(ListNode head){ ListNode temp = null; ListNode newHead = null; ListNode prev = head; while(head != null && head.next != null){ temp = head.next; if(temp.val > head.val){ prev.next = temp; } else { if(newHead == null){ newHead = head; } prev = head; } head = head.next; } return newHead; }