HHot 100C++ 图解

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 i0 2 i1 3 i2 4 i3
链表结构(来自本仓库测试数据)

逐帧动画

1 / 2

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/07_linked_list.cpp19 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q24_swap_pairs8 行
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});

↑↓ 选择↵ 打开/ 随时唤起