Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space. You may not modify the values in the list’s nodes, only nodes itself may be changed.

Table of Contents

Corner cases:

Odd number

Empty linked list

If the linked list is empty, we will return.

sol

Use cur_node.next != None to see if the current node has pair

Use cur_node != None to see if we have reached the end

three place holder node pointer

Cur

Cur points to the current node. It is inited as

Prev points to the node before current node

Order of operations

Use prev ptr to store the previous node and point

Use of dummy head

Get rid of special treatment for head and allow us to use pre at the beginning

Code

    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy_head = ListNode(1)
        dummy_head.next = head
        cur = head
        prev = dummy_head
        if not cur:
            return None

        while cur and cur.next:
            temp = cur.next
            prev.next = temp
            cur.next = temp.next
            temp.next = cur
            prev = cur
            cur = cur.next


        return dummy_head.next

24. Swap Nodes in Pairs