Problem Description
Given a linked list, swap every two adjacent nodes and return its head.
Example 1:
Input: head = [1,2,3,4] Output: [2,1,4,3]
Example 2:
Input: head = [] Output: []
Example 3:
Input: head = [1] Output: [1]
Constraints:
- The number of nodes in the list is in the range
[0, 100]. 0 <= Node.val <= 100
Follow up: Can you solve the problem without modifying the values in the list's nodes? (i.e., Only nodes themselves may be changed.)
The problem description was taken from https://leetcode.com/problems/swap-nodes-in-pairs/.
Problem Solution
#O(N) Time, O(1) Spaceclass Solution: def swapPairs(self, head: ListNode) -> ListNode: dummy = ListNode(0, head) pointer_one, pointer_two = dummy, head while pointer_two and pointer_two.next: pointer_three = pointer_two.next pointer_four = pointer_three.next pointer_three.next = pointer_two pointer_two.next = pointer_four pointer_one.next = pointer_three pointer_one = pointer_two pointer_two = pointer_four return dummy.nextProblem Explanation
In-place swaps or reversals of linked lists will typically come down to a few tasks:
-
Saving a reference to the node of the next iteration
-
Redirecting
.nextpointers
-
Iterating to the previously saved node references
If there is anything to take away from this problem, it is that because this pattern solves many linked list problems.
We will start by creating a dummy node so that we don't have to swap the first pair prior to our traversal.
dummy = ListNode(0, head)
We will then create our first two pointers that will be set at the dummy and the head, respectively.
It may be more helpful for some to rename these variables to words like "prev", and "curr", but this may get confusing after swaps.
pointer_one, pointer_two = dummy, head
Next, we will create a loop for swapping and traversing the linked list.
The loop will run while pointer_two, the first node of each pair group, is not a null node, and also if its next node is not null because then we would not have anything to swap the node with.
while pointer_two and pointer_two.next:
For linked list questions, if we're overwriting node pointers we always want to make sure that we save a bridge to get back across for continuing a traversal down the list.
These bridges are pointer_four and pointer_three.
pointer_three = pointer_two.next pointer_four = pointer_three.next
Here is what our pointers look like right now.
1 2 3 4
->1->2->3->4->None
We will start editing the node's pointers that are furthest down the sublist that we are going to reverse, this is typically how in-place iterative reversals are handled.
We'll go to pointers three, two, one.
Pointer Three
Node two will grab its pointer, disconnect it from node three, turn around and connect it to node one.
pointer_three.next = pointer_two
Pointer Two
Node one will disconnect its pointer from its neighbor two, then throw it over two's head to connect it to node three, replacing the bungee cable that was just removed in the previous step.
pointer_two.next = pointer_four
Pointer One
The dummy node will part with its good friend, node one, disconnect its pointer to node one, and throw it over to its new neighbor, node two.
pointer_one.next = pointer_three
The bungee next pointers will spring into place, swapping the node pair.
1 3 2 4
->2->1->3->4->None
Now we just need to move the pointers down the list to cross the bridge we saved earlier and prepare for the next iteration.
1 2
->2->1->3->4->None
pointer_one = pointer_two pointer_two = pointer_four
Once we have finished swapping each node pair, we will return the list starting with everything after the dummy head, since the first node after the dummy head will be the actual head.
x 2->1->4->3->None