25. K 个一组翻转链表（最详细注释，分成三个步骤进行处理，简单易懂）_k个一组反转单链表

算法描述：

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

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

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

算法思路：

将这道题可以分解成几个部分

以中间情况进行举例

1. 先将自身4-3链表反转
2. 和上一个链表的结尾进行连接
3. 和下一个链表的开始进行连接

然后开始分别解决。

完整代码可直接看文章结尾

先写好循环

while(head!=null){
	// 处理反转
}
1
2
3

1. 将自身反转

使用链表头插法进行自身反转，不同的是这里反转了k个节点就停止。
首先找到这个子链表的开头和结尾，然后略微修改一下头插法即可。
开头不用找，找一下结尾。
定义一个方法getEnd专门用于查结尾。

找结尾节点

// 找到最后一个节点 return null 说明最后已经不够k个了
private ListNode getEnd(ListNode head, int k){
        int index = 1;
        while(head != null){
            head = head.next;
            if(++index == k){
                return head;
            }  
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11

这里有个细节，如果找的是最后一段子链表，且不足k个节点，那就保持原有顺序。所以调用该方法返回值为null即保持原有顺序。

// 获取最后一个节点，用于反转
      ListNode end = getEnd(head,k);
      // 如果到了最后不够了，保持原有顺序，直接返回即可
      if(end == null){
          break;
      }
1
2
3
4
5
6

也就是在此时就可以直接终结循环了。

将自身子链表反转

其实这里就很简单了，结尾节点已知，简单推理一下即可。
定义一个方法reverseList专门用于反转子链表

// 反转head-end之间的链表
     private ListNode reverseList(ListNode head,ListNode end) {
        if(head == null || head.next == null){
            return head;
        }
       
        ListNode next = head.next;
        head.next=null;

        ListNode p;
       
        while(next != null && head != end ){
            p = next.next;
            next.next = head;
            head = next;
            next = p;
        } 
        return head; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在循环中直接调用即可

// 反转本身，head到end反转
       reverseList(head,end);
1
2

需要注意的时候，在调用该方法后，传进来的head，返回的时候已经变成了该子链表的结尾。
传进来的end，返回的时候已经变成了该子链表的开始。

2. 与上一个链表进行连接

那就在记录一下上一个链表的结尾 last 即可，也就是每次处理一个子链表后，将该子链表的结尾，赋给last，用于下一个链表处理。
思考第一个链表的时候，其实last是没有的。那就创建一个保护节点protect，当作最先的last，同时该算法最后返回的时候，直接返回protect.next 即是最终的头节点。意外之喜！

循环前定义last

// 定义一个保护节点
        ListNode protect = new ListNode(0,null);
        ListNode last = protect;
1
2
3

每次处理子链表后，再赋值

// 子链表的开头(现在的end)和上一个链表结尾结合
        last.next = end;
1
2

下一次循环时，last就是该子链表的结尾

// 当前结尾下一个循环时已成上一个链表的结尾（即目前的head）
      last = head;
1
2

3. 与下一个链表进行连接

要记录下一个链表的开头nextGroupStart，但是在处理完子链表后，肯定已经找不到它了，所以在处理前就要先记录。

循环前，定义一下

ListNode nextGroupStart = null;
1

在循环内部，在处理子链表前赋值

// 记录后一个链表的开始
       nextGroupStart = end.next;
1
2

然后在处理完子链表后，再进行连接

// 子链表的结尾(现在的head)和下一个链表开始结合
       head.next = nextGroupStart;
1
2

让下一个子链表开始处理

// 让下一个子链表开始处理吧
       head = nextGroupStart;
1
2

最后，考虑到一些异常情况，比如空指针，k=1或者0的时候其实根本不用处理等等

if(k==1 || k== 0|| head == null || head.next == null){
         return head;
}
1
2
3

最后的最后，直接上完整代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k==1 || k== 0|| head == null || head.next == null){
            return head;
        }
        // 定义一个保护节点
        ListNode protect = new ListNode(0,null);
        ListNode last = protect;
        ListNode nextGroupStart = null;

        // 反转一串链表， 前一个链表的结尾 + 反转本身 + 后一个链表的开始
        while(head!=null){
            // 获取最后一个节点，用于反转
            ListNode end = getEnd(head,k);
            // 如果到了最后不够了，保持原有顺序，直接返回即可
            if(end == null){
                break;
            }
            // 记录后一个链表的开始
            nextGroupStart = end.next;

            // 反转本身，head到end反转
            reverseList(head,end);
            // 子链表的开头(现在的end)和上一个链表结尾结合
            last.next = end;
            // 子链表的结尾(现在的head)和下一个链表开始结合
            head.next = nextGroupStart;

            // 当前结尾下一个循环时已成上一个链表的结尾（现在的head）
            last = head;
            // 让下一个子链表开始处理吧
            head = nextGroupStart;
        }
        return protect.next;


    }
    // 找到最后一个节点 return null 说明最后已经不够k个了
    private ListNode getEnd(ListNode head, int k){
        int index = 1;
        while(head != null){
            head = head.next;
            if(++index == k){
                return head;
            }  
        }
        return head;
    }


    // 反转head-end之间的链表
     private ListNode reverseList(ListNode head,ListNode end) {
        if(head == null || head.next == null){
            return head;
        }
       
        ListNode next = head.next;
        head.next=null;

        ListNode p;
       
        while(next != null && head != end ){
            p = next.next;
            next.next = head;
            head = next;
            next = p;
        } 
        return head; 
    }
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80