Algorithms
Swap alternate nodes in a singly linked list
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;
}