LeetCode Solutions Blog

Swap Nodes in Pairs

Number: 24

Difficulty: Medium

Paid? No

Problem Description

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

Key Insights

Use a dummy node to simplify edge cases, such as when the list is empty or has only one node.
Process nodes in pairs and update the pointers accordingly.
Ensure that the swapping does not lose the connection between the swapped pair and the rest of the list.
The solution can be implemented iteratively or recursively.

Space and Time Complexity

Time Complexity: O(n) - Each node is processed once. Space Complexity: O(1) - Only constant extra space is used.

Solution

We use an iterative approach with a dummy node. The dummy node points to the head of the list. We maintain a pointer that traverses the list in pairs. For each pair, we adjust the next pointers to swap the two nodes. By the end, the dummy's next pointer will be the new head of the modified list. The main idea is to keep track of the previous node (prev) before the pair, and then adjust pointers accordingly using temporary variables to hold references to the nodes being swapped.

Code Solutions

# 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:
        # Create a dummy node and point it to the head of the list.
        dummy = ListNode(0)
        dummy.next = head
        # Initialize the pointer 'prev' to dummy.
        prev = dummy

        # Traverse the list while at least two nodes remain.
        while head and head.next:
            # Identify the two nodes to swap.
            first_node = head
            second_node = head.next

            # Swapping the nodes by reassigning pointers.
            prev.next = second_node          # Link previous node to second node.
            first_node.next = second_node.next  # Link first node to node after second.
            second_node.next = first_node    # Link second node to first to complete swap.

            # Update the pointers for next pair processing.
            prev = first_node                # Move 'prev' pointer to the end of the swapped pair.
            head = first_node.next           # Move 'head' pointer to the next pair.

        # Return the new head of the list.
        return dummy.next