24. Swap Nodes in Pairs

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.

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax