Swap Nodes in Pairs

LeetCode Link: 24. Swap Nodes in Pairs

Problem Definition

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

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

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

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

Thought Process

It is recommended to use a dummy head node, which will make it much more convenient. Otherwise, you would have to handle the head node separately each time (since there isn't a previous pointer pointing to the head node).

If you're not familiar with operations on dummy head nodes, you can refer to this article.

Remove Linked List Elements

Learn three efficient approaches to remove nodes with a specific value from a linked list in Python. Explore direct removal, dummy head node, and recursive solutions. Complete with time/space complexity analysis and detailed examples. Perfect for coding interviews and data structure mastery.

Fanyang Meng's BlogFanyang Meng

Next, it's time to swap two adjacent elements. At this point, you must draw a diagram; without it, handling multiple pointers can easily become confusing, especially regarding the order of operations.

Initially, cur points to the dummy head node and then follows these three steps:

After the operation, the linked list is as follows:

Solution 1 - Dummy Head

# 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:
        # Edge cases: empty list or single node
        if not head or not head.next:
            return head
            
        # Create a dummy node to handle edge cases more elegantly
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        
        while prev.next and prev.next.next:
            # Node positions for swapping
            first = prev.next
            second = first.next
            
            # Perform the swap
            first.next = second.next
            second.next = first
            prev.next = second
            
            # Move to the next pair
            prev = first
            
        return dummy.next

Time Complexity: O(n)

Space Complexity: O(1)

Solution 2 - Recursion

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # Base case: if the list is empty or has only one node, no swap is needed
    if not head or not head.next:
        return head
    
    # Identify nodes for swapping
    first_node = head          # The first node of the pair
    second_node = head.next    # The second node of the pair
    rest_of_list = head.next.next  # The rest of the list after the pair
    
    # Step 1: Swap the pair
    second_node.next = first_node  # The second node points to the first node
    
    # Step 2: Recursively swap the rest of the list in pairs
    first_node.next = self.swapPairs(rest_of_list)  # Connect the swapped pair with the next pairs
    
    # Return the new head of the list, which is the second node in the current pair
    return second_node

Comparison Summary