LeetCode 24: Swap Nodes in Pairs (Iterative Pointer Rewiring)
LeetCode 24Linked ListPointersIterationToday we solve LeetCode 24 - Swap Nodes in Pairs.
Source: https://leetcode.com/problems/swap-nodes-in-pairs/
English
Problem Summary
Given the head of a singly linked list, swap every two adjacent nodes and return the new head. You must swap nodes (pointer links), not values.
Key Insight
For each local pattern prev -> a -> b -> nextPair, rewiring to prev -> b -> a -> nextPair is enough. A dummy head makes the first pair identical to all later pairs.
Brute Force and Limitations
A recursive approach naturally swaps one pair and delegates the rest. It is elegant, but uses call stack O(n). Iterative rewiring achieves the same logic with O(1) extra space.
Optimal Algorithm Steps
1) Create dummy.next = head, set prev = dummy.
2) While prev.next and prev.next.next exist, let a = prev.next, b = a.next.
3) Rewire: a.next = b.next, b.next = a, prev.next = b.
4) Move prev = a to the next pair boundary and continue.
Complexity Analysis
Time: O(n), each node is touched constant times.
Space: O(1).
Common Pitfalls
- Swapping values instead of nodes (violates problem intent).
- Forgetting to reconnect prev.next to the new pair head b.
- Advancing prev incorrectly (must move to old first node a after swap).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, 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;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
prev := dummy
for prev.Next != nil && prev.Next.Next != nil {
a := prev.Next
b := a.Next
a.Next = b.Next
b.Next = a
prev.Next = b
prev = a
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0, 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;
}
};# 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 | None') -> 'ListNode | None':
dummy = ListNode(0, 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.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var swapPairs = function(head) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next !== null && prev.next.next !== null) {
const a = prev.next;
const b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
};中文
题目概述
给定单链表头节点，每两个相邻节点交换一次并返回新头节点。要求交换的是节点连接关系，不是节点值。
核心思路
局部结构 prev -> a -> b -> nextPair，交换后变为 prev -> b -> a -> nextPair。引入虚拟头节点后，首对节点与中间节点可用同一套逻辑处理。
朴素解法与不足
递归做法可先交换前两个，再处理后续子链表，写起来简洁，但会占用 O(n) 递归栈。迭代指针重连可将额外空间降到 O(1)。
最优算法步骤
1）创建 dummy.next = head，令 prev = dummy。
2）当 prev.next 与 prev.next.next 都存在时，定义 a = prev.next、b = a.next。
3）按顺序重连：a.next = b.next，b.next = a，prev.next = b。
4）令 prev = a，继续处理下一对节点。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 只交换节点值而不是节点指针。
- 忘记把 prev.next 指回交换后的新头 b。
- 交换后 prev 移动错误，必须移动到旧的首节点 a。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, 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;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
prev := dummy
for prev.Next != nil && prev.Next.Next != nil {
a := prev.Next
b := a.Next
a.Next = b.Next
b.Next = a
prev.Next = b
prev = a
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0, 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;
}
};# 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 | None') -> 'ListNode | None':
dummy = ListNode(0, 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.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var swapPairs = function(head) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next !== null && prev.next.next !== null) {
const a = prev.next;
const b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
};
Comments