Kinda like reversing a linked list, except we reverse every two nodes. How do we accomplish this? As always, maintaining a dummy node helps us start the process. The dummy node will point to the head of the linked list, and be used to keep track of the pairs as we process them.
Next, we acquire a pointer to the first node and the second node. We point dummy node to the second node as it’s about to become the new head. We then point the first node to the second node’s next node. Then we point the second node to the first node. The two nodes have been swapped at this point.
Finally, we set the prev node to the first node, which is now techincally the second node in the pair. We then set the head to the first node of the next pair. We repeat until head.next or head is None. We finally return dummy.next which is the head of the linked list.
The solution is as follows:
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
prev_node = dummy
while head and head.next:
first_node = head
second_node = head.next
prev_node.next = second_node
first_node.next = second_node.next
second_node.next = first_node
prev_node = first_node
head = first_node.next
return dummy.next_ Time Complexity:
O(n) - We traverse all nodes within the linked list.
_ Space Complexity:
O(1) - We create one dummy node and a few pointers to traverse the linked list.