24. 两两交换链表中的节点
一句话套路dummy + 每次交换相邻一对
题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
提示:
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
思路
时间
O(n)空间
O(1)。递归写法更短但栈空间 O(n)。思路
每轮关注 4 个指针:prev、first、second、third。
改链顺序
prev->next=second; second->next=first; first->next=third。
交换后 prev 要前进两步(移动到 first 的位置),它就是下一组的 prev。
图解
链表结构(来自本仓库测试数据)
逐帧动画
1 / 2
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0024 {
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
while (prev->next && prev->next->next) {
ListNode* first = prev->next;
ListNode* second = first->next;
first->next = second->next;
second->next = first;
prev->next = second;
prev = first; // 交换后 first 已是本组尾部
}
return dummy.next;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0024::Solution s;
ListNode* a = buildList({1, 2, 3, 4});
CHECK_EQ(listToVec(s.swapPairs(a)), vector<int>{2, 1, 4, 3});
ListNode* b = buildList({1, 2, 3}); // 奇数个,落单的不换
CHECK_EQ(listToVec(s.swapPairs(b)), vector<int>{2, 1, 3});
CHECK_TRUE(s.swapPairs(nullptr) == nullptr);
ListNode* c = buildList({7});
CHECK_EQ(listToVec(s.swapPairs(c)), vector<int>{7});