24. Swap Nodes in Pairs

Problem

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.

Example:

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

Thought Process

  • 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

White Board

Below is the white board:

Code

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                                   

Complexity

  • Time complexity is O(n), space complexity is O(n) as well

Optimization

TODO How to improve?