LeetCode 24: Swap Nodes in Pairs Solution in Python

LeetCode 24 is a coding challenge titled “Swap Nodes in Pairs,” and it requires us to swap every two adjacent nodes in a singly linked list without altering the nodes’ values directly. This means we must rearrange the linked list’s nodes themselves by redirecting the connecting pointers.

# 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 not head:
        return head
      
      temp1 = head
      temp2 = head.next
      prev = None
      head_updated = False

      while temp1 and temp2:
        temp1.next = temp2.next
        temp2.next = temp1
        if prev:
          prev.next = temp2
        # Only applies after the first swap
        if not head_updated:
          head = temp2
          head_updated = True
        # Move the pointers temp1 and temp2
        prev = temp1
        temp1 = temp1.next
        if temp1:
          temp2 = temp1.next
      
      return head

Python Solution Logic

My Python algorithm for the Swap Nodes in Pairs LeetCode solution employs a step-by-step approach to swap every two adjacent nodes in a given linked list without altering the node values. This involves manipulating the pointers of the nodes to rearrange their order. Here’s a detailed explanation of how this Python code works:

Firstly, let’s go through the node definition for this LeetCode problem in Python. The ListNode class is a basic structure for each node in the linked list, containing a val attribute for the node’s value and a next pointer to the next node in the list. The Solution class contains the method swapPairs, which takes the head of a linked list as input and returns the head of the modified list after swapping pairs.

Now, onto the meat of my Python solution. The method first checks if the input head is None (i.e., the list is empty) and returns it immediately, as there’s nothing to swap in an empty list.

• The variables temp1 and temp2 are initialized to point to the first and second nodes of the list, respectively.
• prev is initialized to None and will eventually point to the node preceding the current pair being swapped.
• head_updated is a boolean flag used to update the list’s head on the first swap.

Swapping Logic

Regarding swapping the nodes, the code enters a while loop that continues as long as temp1 and temp2 (the pair of nodes to be swapped) are not None. Inside the loop, temp1‘s next pointer is updated to point to the node after temp2, thus removing temp1 from its initial position.

temp2‘s next pointer is then set to temp1, placing temp2 before temp1 and completing the swap. If prev is not None (i.e., this is not the first pair being swapped), its next pointer is updated to point to temp2, linking the previous pair with the current swapped pair. On the first iteration, the head of the list is updated to temp2 since the first node has changed due to the swap. The head_updated flag ensures this operation only happens once.

Moving the Two Pointers

After swapping a pair, prev is set to temp1 (the node that was originally the first in the pair and is now second). Meanwhile, temp1 is advanced to the next node in the list, and temp2 is updated to be the node after temp1, preparing for the next swap.

The loop continues until there are no more pairs to swap (i.e., when temp1 is None or temp1.next is None). The modified list’s head, which might have been updated during the first swap, is returned.

Time Complexity: O(n)

The core of the algorithm involves a single pass through the linked list to swap adjacent pairs. During this pass, each node is visited exactly once to either swap it with its adjacent node or move the pointers accordingly. Given that n represents the total number of nodes in the list, the algorithm’s time complexity is O(n), which is linear time complexity. Incidentally, each operation inside the loop (like swapping pointers) is considered to have a constant time complexity.

Space Complexity: O(1)

The algorithm modifies the linked list in place and only uses a fixed number of pointers (temp1, temp2, and prev) regardless of the input size. These pointers are used to track the current pair of nodes being swapped and the node immediately preceding this pair. The head_updated boolean flag is also used to mark the first swap operation, ensuring the list’s head is updated correctly. Since the solution does not utilize recursion or allocate additional data structures that grow with the size of the input, the amount of extra memory required does not scale with the number of nodes in the linked list. This results in a constant space complexity, O(1), highlighting the in-place nature of the swapping mechanism.

As an exercise, try replicating the logic of my Python Solution for LeetCode’s Swap Nodes in Pairs problem using other programming languages, such as C++ or Java.