Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Given 1->2->3->4, you should return the list as 2->1->4->3.
- For every node pair: front and back
- front’s next will be pointed to the back’s next
- back’s next will be pointed to the front
- front’s previous node’s next will be pointed to back
- Setting up a dummy head node will be helpful
Below is the white board:
class LN: def __init__(self, val): self.val = val self.next = None class Sol: def swapPairs(self, head): # create a dummy head, use -1 as default dh = LN(-1) dh.next = head # create a pointer index based off dh idx = dh while (idx.next and idx.next.next): # initialize the nodes for pair swap n1 = idx.next n2 = n1.next nxt = n2.next # swap pairs n2.next = n1 n1.next = nxt idx.next = n2 # updated index dh = idx.next.next # return the head node return dh.next
- Time complexity is O(n), space complexity is O(1)