Leetcode: Swap node in pairs

Swap Nodes in Pairs | LeetCode OJ

We will use a dummy head and avoid checking for empty input.

1. Go to the third node
2. Use 2 pointers to mark the first and second node
3. Between the dummy head and the third node, swap the first 2 nodes
4. Move 2 steps ahead to make the next swap

Remarks:

1. O(n) time complexity, for iterating the list
2. O(1) space complexity for using 3 additional pointers
3. Using dummy head to make processing easier

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

def swapPairs(self, head):
    prev, prev.next = ListNode(0), head
    head = prev
    while prev.next and prev.next.next:
        p = prev.next
        q = p.next
        prev.next, q.next, p.next = q, p, q.next
        prev = p
    return head.next