[LeetCode] 024. Swap Nodes in Pairs

April 01, 2019 - Monday

Algorithm

leetcode

python

Problem
Approach 1: Recursive Swap Pointers (My Solution)
- Idea
- Solution
- Complexity

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.

Approach 1: Recursive Swap Pointers (My Solution)

Idea

Swap each pair as a single process in the recursion.

Solution

# Definition for singly-linked list.
#    def __init__(self, x):
#        self.val = x
#        self.next = None

class Solution1:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def helper(head, parent=None):
            h0 = head.next
            if not parent:
                h = head
                if h.next:
                    tmp = h.next.next
                    h.next.next = h
                    h.next = tmp
                    if tmp:
                        helper(head, h)
            else:
                h = parent.next
                if h.next:
                    tmp = h.next.next
                    h.next.next = h
                    parent.next = h.next
                    h.next = tmp
                    if tmp:
                        helper(head, h)
            return h0
        if not head or not head.next:
            return head
        else:
            return helper(head) 

Complexity

Time: $O(n)$
Space: $O(1)$