### LeetCode

# LeetCode 24: Swap Nodes in Pairs Solution in Python

Swap adjacent nodes in a linked list with linear time and constant space complexity, using pointer manipulation for efficient in-place node rearrangement.

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

represents the total number of nodes in the list, the algorithm’s time complexity is **n****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.