题目描述：

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

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

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

img

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

img

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

思路

关键点：

  • 局部翻转
  • k > 剩余局部链表长度时，这部分链表无需翻转

步骤：

  1. 初始化

    ListNode dummy = new ListNode(0,head);

  2. 设置指针实现局部翻转

    ListNode pre = dummy,end = dummy

  3. end.next != null 则遍历链表

    1. 根据k确定第一组局部链表的尾部指针

      for(int i = 0; i < k && end != null; i++) end = end.next;

      此时end == null时，说明剩余的局部链表长度小于k，直接跳出循环无需翻转链表。

    2. 确定局部链表起始位置及下一组的起始位置

      1
      2
      start = pre.next;
      next = end.next;

    3. 断开end的后续链表，并调用翻转函数使pre.next连接翻转后的链表。

      pre.next = reverse(start);

    4. 重新连接被翻转和未翻转的部分

      1
      2
      3
      start.next = next;//连接后面未翻转的链表
      pre = next;//重置pre和end指针开始新的一轮链表组的翻转
      end = pre;

  4. 返回dummy后面所有已经翻转的链表

关键代码

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
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, end = dummy;
        while(end.next != null){
            for(int i = 0; i < k && end != null; i++){
                end = end.next;
            }
            if(end == null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null; 
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return dummy.next;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}