### View *Swap Nodes in Pairs* on LeetCode

## Statistics

**Time Spent Coding**

20 minutes

**Time Complexity**

O(n) - The algorithm must iterate through each node in the list at least once and perform O(1) operations at each node, resulting in the O(n) time complexity.

**Space Complexity**

O(1) - The number of variables created is independent of the length of the input list, resulting in the O(1) space complexity.

**Runtime Beats**

94.79% of other submissions

**Memory Beats**

92.32% of other sumbissions

## Explanation

Before performing logic, verify that the `head`

node is not any and that `head.next`

is not any; if the conditions are not met, then `return head.`

If the conditions are met, save the `adjacent`

and `next_pair`

nodes. `next_pair`

is the `head`

node of the next pair that will be used as an argument for the recursive call of the function. Assign `adjacent.next`

to point at the head node and `head.next`

to point at the recursive function call because the next node may change after another iteration of `swapPairs`

and must not be statically assigned.

Once the recursive calls end, `head.next`

will be appropriately assigned and connected with the other swapped pairs. Since the algorithm is complete, return the new head of the list `adjacent.`

This is because `head`

and `adjacent`

swapped places, and if this line is omitted, the algorithm will not successfully connect each pair after termination and leave many dangling pointers.

## Data Structure Used

**Linked List -** Similar to a list or an array, except the data allocated for the list is generated as each new node is added, meaning the memory for the entire list may not be in consecutive memory. A linked list can not be indexed and must be traversed using a pointer.

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 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 or not head.next: return head
adjacent = head.next
next_pair = adjacent.next
adjacent.next = head
head.next = self.swapPairs(next_pair)
return adjacent