LeetCode 24. Swap Nodes in Pairs

Description

https://leetcode.com/problems/swap-nodes-in-pairs/

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

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Follow up: Can you solve the problem without modifying the values in the list’s nodes? (i.e., Only nodes themselves may be changed.)

Explanation

We can resolve the problem with a recursive approach.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        return self.helper(head)
            
    def helper(self, head):
        if not head:
            return head
        
        if not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        
        
        third = head.next.next
        
        dummy.next = head.next
        head.next.next = head        
                        
        head.next = self.helper(third)

           
        return dummy.next

• Time Complexity: O(N)
• Space Complexity: O(N)