Swap Nodes in Pairs solution and explanation
Google
9 more videos on this problem
Swap Nodes in Pairs - Apple Interview Question - Leetcode 24NeetCode · 8:43 · 89K views
LeetCode Swap Nodes in Pairs Explained - JavaNick White · 4:05 · 40K views
Swap Nodes in Pairs (LeetCode 24) | Full solution with animations diagrams | Study AlgorithmsNikhil Lohia · 15:04 · 30K views
Swap Nodes in Pairs | Live Coding with Explanation | Leetcode - 24Algorithms Made Easy · 7:30 · 15K views
Swap Nodes in Pairs | | MICROSOFT, AMAZON | Leetcode-24 | Live Code + Explanation 🧑🏻💻👩🏻💻codestorywithMIK · 15:39 · 13K views
Swap Nodes in Pairs | leetcode 24 | Company tag : Amazon, Microsoft, Facebook | Pythonthecodingworld · 8:59 · 8K views
Swap Nodes in Pairs | Leet code 24 | Theory explained + Python codeSai Anish Malla · 14:25 · 1K views
LeetCode 24 | Swap Nodes in Pairs | Solution Explained (Java + Whiteboard)Xavier Elon · 7:00 · 1K views
Swap Nodes in Pairs - Leetcode 24 - PythonTechError · 9:38 · 1K views
Swap Nodes in Pairs - LeetCode 24 - Coding Interview QuestionsOne Code Man · 5:01 · 1K views
The problem
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
Approach overview
Problem Overview: You receive the head of a singly linked list and must swap every two adjacent nodes. The swap must change node pointers, not node values. For example, 1→2→3→4 becomes 2→1→4→3. If the list length is odd, the final node remains unchanged.
Approach 1: Iterative Pointer Manipulation (O(n) time, O(1) space)
This approach walks through the list while swapping nodes in pairs using pointer updates. Maintain a dummy node before the head to simplify edge handling. For each pair, identify first and second, then update three pointers: connect the previous node to second, point first.next to the node after the pair, and set second.next to first. Move the pointer forward by two nodes and repeat. Every node is visited once, giving O(n) time with constant extra memory O(1). This is the most practical technique when working with linked list pointer manipulation.
Approach 2: Recursive Pair Swapping (O(n) time, O(n) space)
The recursive solution treats the list as a sequence of pairs. The base case occurs when the list has zero or one node remaining. For each recursive call, swap the first two nodes: let second become the new head of the pair, then recursively process the remaining list starting from head.next.next. After the recursive call returns, attach the result to head.next. Each call processes exactly one pair, so the algorithm still runs in O(n) time. The recursion stack stores up to n/2 calls, resulting in O(n) auxiliary space. This version highlights structural thinking often used in recursion problems involving linked structures.
Recommended for interviews: The iterative pointer solution is usually the expected answer. Interviewers want to see that you can safely manipulate linked list pointers without breaking the chain. The recursive version demonstrates good conceptual understanding of pairwise decomposition, but the iterative approach is preferred because it avoids stack overhead and keeps space complexity at O(1).
Approach 1: Iterative Approach
This approach uses iteration to systematically swap each pair of adjacent nodes in the linked list. The main idea is to traverse the list while keeping track of pointers to the nodes before and after the pair being swapped. By adjusting these pointers, we effectively swap nodes without modifying their values.
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
a = prev.next
b = a.next
a.next = b.next
b.next = a
prev.next = b
prev = a
return dummy.nextclass Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode a = prev.next;
ListNode b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}
}class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(-1);
dummy.next = head;
ListNode* prev = &dummy;
while (prev->next && prev->next->next) {
ListNode* a = prev->next;
ListNode* b = a->next;
a->next = b->next;
b->next = a;
prev->next = b;
prev = a;
}
return dummy.next;
}
};var swapPairs = function(head) {
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy;
while (prev.next !== null && prev.next.next !== null) {
let a = prev.next;
let b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode dummy;
dummy.next = head;
struct ListNode* prev = &dummy;
while (prev->next && prev->next->next) {
struct ListNode* a = prev->next;
struct ListNode* b = a->next;
a->next = b->next;
b->next = a;
prev->next = b;
prev = a;
}
return dummy.next;
}public class Solution {
public ListNode SwapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode a = prev.next;
ListNode b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}
}This Python solution also leverages a dummy node to conveniently handle potential changes to the head node. The prev pointer iterates through the list, and within the loop, pointers are reassigned to swap each pair of nodes, making sure to continue the swap process with prev set at the end of the current pair.
Python's dynamic typing and straightforward list node management makes this implementation quite elegant and succinct.
Time Complexity: O(n), as every node is visited once.
Space Complexity: O(1), only constant space is used apart from the input variables.
Approach 2: Recursive Approach
This approach leverages recursion to swap every two adjacent nodes. The key idea is to break the problem into subproblems where you solve for a pair and recursively call to solve for the next. The recursion naturally handles the base case where less than two nodes remain to be swapped.
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
newHead = head.next
head.next = self.swapPairs(newHead.next)
newHead.next = head
return newHeadclass Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};var swapPairs = function(head) {
if (head === null || head.next === null) return head;
let newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* swapPairs(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}public class Solution {
public ListNode SwapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = SwapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}The Python function checks if there are fewer than two nodes left, returning the head. It takes head.next, which is the new head in the swapped pair, and performs a recursive call on the list starting after the next node, setting the returned result to head.next.
This recursive setup effectively 'switches' the pairs and uses the call stack to finish the swaps for the entire list.
Time Complexity: O(n), since we process each node recursively.
Space Complexity: O(n), accounting for the recursive call stack.
Approach 3: Recursion
We can implement swapping two nodes in the linked list through recursion.
The termination condition of recursion is that there are no nodes in the linked list, or there is only one node in the linked list. At this time, swapping cannot be performed, so we directly return this node.
Otherwise, we recursively swap the linked list head.next.next, and let the swapped head node be t. Then we let p be the next node of head, and let p point to head, and head point to t, finally return p.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function swapPairs(head: ListNode | null): ListNode | null {
if (!head || !head.next) {
return head;
}
const t = swapPairs(head.next.next);
const p = head.next;
p.next = head;
head.next = t;
return p;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
t := swapPairs(head.Next.Next)
p := head.Next
p.Next = head
head.Next = t
return p
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
let mut cur = dummy.as_mut().unwrap();
while cur.next.is_some() && cur.next.as_ref().unwrap().next.is_some() {
cur.next = {
let mut b = cur.next.as_mut().unwrap().next.take();
cur.next.as_mut().unwrap().next = b.as_mut().unwrap().next.take();
let a = cur.next.take();
b.as_mut().unwrap().next = a;
b
};
cur = cur.next.as_mut().unwrap().next.as_mut().unwrap();
}
dummy.unwrap().next
}
}# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val = 0, _next = nil)
# @val = val
# @next = _next
# end
# end
# @param {ListNode} head
# @return {ListNode}
def swap_pairs(head)
dummy = ListNode.new(0, head)
pre = dummy
cur = head
while !cur.nil? && !cur.next.nil?
t = cur.next
cur.next = t.next
t.next = cur
pre.next = t
pre = cur
cur = cur.next
end
dummy.next
endApproach 4: Iteration
We set a dummy head node dummy, initially pointing to head, and then set two pointers pre and cur, initially pre points to dummy, and cur points to head.
Next, we traverse the linked list. Each time we need to swap the two nodes after pre, so we first judge whether cur and cur.next are empty. If they are not empty, we perform the swap, otherwise we terminate the loop.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function swapPairs(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let [pre, cur] = [dummy, head];
while (cur && cur.next) {
const t = cur.next;
cur.next = t.next;
t.next = cur;
pre.next = t;
[pre, cur] = [cur, cur.next];
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre, cur := dummy, head
for cur != nil && cur.Next != nil {
t := cur.Next
cur.Next = t.Next
t.Next = cur
pre.Next = t
pre, cur = cur, cur.Next
}
return dummy.Next
}# Definition for singly-linked list.
# class ListNode {
# public $val;
# public $next;
# public function __construct($val = 0, $next = null)
# {
# $this->val = $val;
# $this->next = $next;
# }
# }
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function swapPairs($head) {
$dummy = new ListNode(0);
$dummy->next = $head;
$prev = $dummy;
while ($head !== null && $head->next !== null) {
$first = $head;
$second = $head->next;
$first->next = $second->next;
$second->next = $first;
$prev->next = $second;
$prev = $first;
$head = $first->next;
}
return $dummy->next;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n), as every node is visited once. Space Complexity: O(1), only constant space is used apart from the input variables. |
| Recursive Approach | Time Complexity: O(n), since we process each node recursively. Space Complexity: O(n), accounting for the recursive call stack. |
| Recursion | – |
| Iteration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Pointer Manipulation | O(n) | O(1) | Best general solution; efficient pointer updates without recursion |
| Recursive Pair Swapping | O(n) | O(n) | Useful for practicing recursive reasoning on linked list structures |
Frequently asked questions
Is Swap Nodes in Pairs easy or hard?
Swap Nodes in Pairs is generally classified as a medium difficulty problem. The challenge comes from correctly updating multiple pointers without breaking the linked list chain, especially when handling the head and the remaining nodes.
How to solve Swap Nodes in Pairs in O(n)?
Traverse the linked list while processing two nodes at a time. Use a dummy node before the head, then repeatedly swap the pair by updating pointers: connect the previous node to the second node, set second.next to the first, and move forward by two nodes. This processes the entire list in O(n) time.
Swap Nodes in Pairs Python or Java solution
Python and Java implementations typically use the same pointer logic. Create a dummy node before the head, iterate while two nodes exist, and update pointers to swap the pair. Python uses object references directly, while Java manipulates ListNode objects in the same pattern.
What is the best approach for Swap Nodes in Pairs?
The iterative pointer manipulation approach is considered the best solution. It traverses the linked list once while swapping adjacent nodes using constant extra memory. Time complexity is O(n) and space complexity is O(1), which makes it optimal for production and interview scenarios.
Is Swap Nodes in Pairs asked at Google Amazon Meta?
Swap Nodes in Pairs is a classic linked list manipulation problem frequently used in technical interviews. Variants of this question appear in interviews at companies like Amazon, Meta, and Google to test pointer handling and understanding of linked list structure.
What data structure is used in Swap Nodes in Pairs?
The problem uses a singly linked list. The main operations involve pointer manipulation, specifically updating the next references of nodes to reverse each adjacent pair without modifying node values.
What is the time complexity of Swap Nodes in Pairs?
Both the iterative and recursive solutions run in O(n) time because each node in the linked list is processed once. The iterative method uses O(1) extra space, while the recursive approach requires O(n) space due to the recursion call stack.