HHot 100C++ 图解

25. K 个一组翻转链表

困难 链表 在力扣上做

一句话套路数够 k 个就整组反转,再串接

题目描述

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

 

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

 

提示:
  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

 

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

思路

时间O(n)
空间O(1)

思路

先探路确认剩余够 k 个(不够就保留原序),再反转这一组。

反转时把 prev 初值设为 groupNext,反转完自然接上了后段。

groupPrev 只在本组完成后前移一次,移到「本组原来的尾结点」。

易错

反转后本组的头尾互换,记 tail = 原头 才能正确接下一组。

图解

1 i0 2 i1 3 i2 4 i3 5 i4
链表结构(来自本仓库测试数据)

C++17 题解

src/07_linked_list.cpp28 行
namespace lc0025 {
class Solution {
 public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* groupPrev = &dummy;
    while (true) {
      ListNode* kth = groupPrev;
      for (int i = 0; i < k && kth; ++i) kth = kth->next;
      if (!kth) break;                       // 不足 k 个,保持原序
      ListNode* groupNext = kth->next;
      ListNode* prev = groupNext;            // 反转时组尾直接接上后段
      ListNode* cur = groupPrev->next;
      while (cur != groupNext) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
      }
      ListNode* groupTail = groupPrev->next;  // 旧的组头,现在是组尾
      groupPrev->next = kth;                  // 新的组头接到前一段
      groupPrev = groupTail;
    }
    return dummy.next;
  }
};
}

单元测试

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

TEST q25_reverse_k_group9 行
lc0025::Solution s;
ListNode* a = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.reverseKGroup(a, 2)), vector<int>{2, 1, 4, 3, 5});
ListNode* b = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.reverseKGroup(b, 3)), vector<int>{3, 2, 1, 4, 5});
ListNode* c = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.reverseKGroup(c, 1)), vector<int>{1, 2, 3, 4, 5});
ListNode* d = buildList({1, 2, 3});
CHECK_EQ(listToVec(s.reverseKGroup(d, 4)), vector<int>{1, 2, 3});  // k 超过长度

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