24. Swap Nodes in Pairs

Medium

Problem:

Swap every pair of nodes in the linked list given as input.

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

What to learn:

Swapping the values

You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

# 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: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        
        while cur and cur.next:
            cur.val, cul.next.val = cur.next.val, cur.val
            cur = cur.next.next
        return head

Solution:

Interative

1. Set 'b' to point to the head, and the head to point to the next node of 'b'.

2. Set the previous node of 'head' ('prev') to point to 'b'.

3. For the next comparison, move the head one step forward, and 'prev' two steps forward.

4. Since this solution directly modifies the node pointing to the head of the linked list, it can't return the head. Instead, it sets a node called 'root' to precede the head, and then returns 'root.next'.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        root = prev = ListNode(None)
        prev.next = head
        
        while head and head.next:
            b = head.next
            head.next = b.next
            b.next = head
            
            # prev -> b
            prev.next = b
            
            # Move
            head = head.next
            prev = prev.next.next
        
        return root.next

Recursive

The recursive solution uses fewer unnecessary variables, resulting in lower space complexity, and it has a tight and well-structured code.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if head and head.next:
            p = head.next
            head.next = self.swapPairs(p.next)
            p.next = head
            return p
        return head