25_K个一组翻转链表

难度：困难

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

  • 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例

示例一：

img

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

示例二：

img

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

示例三：

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

示例四：

输入：head = [1], k = 1
输出：[1]

提示

  • 列表中节点的数量在范围 sz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

解题

提到翻转首先想到 stack 的特点，入栈再出栈即可实现翻转。

这题也是一样，循环 k 次，先入栈，如果不足 k 次，则不反转，原链表顺序不变。

重新定义一个链表 dummy，定义一个链表尾 ListNode p = dummy

每轮循环记录一个 head，这个 head 作为小组的头节点，然后定义临时变量 ListNode temp = head，入栈后 temp = temp.next , 当剩余不足 k 个时，链表尾直接接小组头 p.next = head ,如果足够 k 个，则开始出栈，p.next = stack.pollLast()； p = p.next，出栈结束后更新下小组的头节点head = temp

最后返回链表头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public ListNode reverseKGroup(ListNode head, int k) { 
  Deque<ListNode> stack = new ArrayDeque<>();
  // 链表头
  ListNode dummy = new ListNode(0);
  // 链表尾
  ListNode p = dummy;
  while (true){
    int count = 0;
    ListNode temp = head;
    // 向 stack 里推入 k 个
    while (temp != null && count < k){
      stack.add(temp);
      temp = temp.next;
      count++;
    }
    // 不足 k 个，直接连在 p 后面
    if (count != k){
      p.next = head;
      break;
    }
    // 出栈
    while (!stack.isEmpty()){
      p.next = stack.pollLast();
      p = p.next;
    }
    //
    head = temp;
  }
  // 返回链表头的下一个
  return dummy.next;
}