LeetCode 1721: Swapping Nodes in a Linked List

This is one of those problems that can actually tell the good programmers from the muggles.

The problem is an amalgamation of two common Linked List problems:
1. Find the kth node from the end in a Linked List.
2. Swap nodes in a linked list.

Solve these two sub-problems, and you solve the main problem.

How to approach the solution? Since we ultimately need to swap the nodes, we need to keep track of the current and the previous pointers.

We’ll use the following references:

// Pointer to kth node from the beginning
ListNode beg = head; 
// Pointer to the previous node of the kth node from the beginning
ListNode prevBeg = null;
// Pointer to kth node from the end
ListNode end = head;
// Pointer to the previous node of the kth node from the end
ListNode prevEnd = null

Let’s get beg and prevBeg in place first.

// kth node from the beginning will require k - 1 iterations
int counter = k - 1;
while(counter-- > 0) {
    prevBeg = beg;
    beg = beg.next;
}

Now beg points to the kth node from the beginning, and prevBeg points to beg’s previous node.

To find the kth node from the end, initialize a pointer ptr to beg, and keep incrementing both ptr and end. When ptr reaches the last node, end will have reached the kth node from the end.

If you are unfamiliar with this concept, please read about kth node from the end online. Plenty of good articles online.

ListNode ptr = beg;
while(ptr.next != null) {
    prevEnd = end;
    end = end.next;
    ptr = ptr.next;
}

Now that we have all our pointers in place, we will proceed to sub-problem 2 : Swapping the nodes. Swapping can be done the easy way and the hard way.

1. Easy way : Just swap the the data of the nodes like a noob.
2. Hard way : Swap the nodes by rewiring the pointers.

If asked in an interview, please do yourself a favor and do it the hard way.

Before swapping we need to consider all the possible scenarios :
1. beg and end could be the head/tail nodes.
2. beg and end could be adjacent to each other. (Example k = 3 where list size is 6)
3. Neither 1 nor 2. (Example k = 2 where list size is 5)

How to execute the swap?
1. First swap the next pointers of the previous pointers (prevBeg and prevEnd)
2. Then swap the next pointers of the current pointers (beg and end).

/*
If prevBeg is still null, it means k was 1 (as our first loop did not run even once). In this case the new head will be end.
*/
if(prevBeg == null) {
    head = end;
} else {
    prevBeg.next = end;
}
/*        
If prevEnd is still null, it means k was N (our second loop did not run even once, as ptr.next was null, as beg was at last node)
In this case the new head will be beg. (Since beg has reached the last node, which should be the new head)
*/
if(prevEnd == null) {
    head = beg;
} else {
    prevEnd.next = beg;
}
    
// Now swap the nexts of current nodes. 
ListNode temp = beg.next;
beg.next = end.next;
end.next = temp;

There you go! Pat yourself on the back now. You’re one step closer to your goal.

Peace.