leetcod 25：K个一组反转链表(思路很直接，但是处理细节较多的hard题)_头插法反转k个

题解

• 题目：给定链表的头和整数k，k小于链表长度，要求对链表中每k个节点进行一次翻转，如示例所示
  
• 题解：这题是翻转链表的拓展版。
  • 主要思路：针对每个长度为k的子链（简称k链）进行一个翻转，将前一个k链的末尾节点连接上下一个k链的开头节点。
  • 首先是如何找到k链，方法有不少，但是最实用的方法就是设置头指针和尾指针，尾指针指向第k个节点即可。
  • 找到k链之后，就是进行翻转操作，这里使用头插法，链表翻转就不多介绍了。
  • 最后就是讨论如何连接上一个k链和下一个k链的问题了。主要有两个方面。
    • 首先最简单的，就是k链翻转之后，会丢失指向下一个k链头节点的next指针，因此我们需要使用nxt通过顺序遍历k+1次预先记录这一个节点。
    • 其次就是对于两个需要连接的k链来说，这两个必须是已经翻转过的k链，比如1->2->3->4->5，k=2，要连接前两个k链的时候，必须是2->1，4->3，也就是连接1->4形成2->1->4->3，否则如果先连接，再翻转，就是现有2->1->3->4然后再翻转之后就成了2->1->3<-4，此时4节点就丢失了指向它的节点。
  • 这里的解决方法其实和头插法比较相似，就是我们需要事先使用pre节点记录好上一个k链的尾部节点，在这一次翻转完之后，再将上一次的pre指向这一次翻转完之后的头部，这样就可以完成前后相连的问题了。
• 实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reverseList(ListNode head, ListNode tail){
            ListNode prev = null;
            ListNode p = head;
            while(prev!=tail){
                ListNode nxt = p.next;
                p.next = prev;
                prev = p;
                p = nxt;
            } 
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k < 2) {
            return head;
        }
        ListNode node = new ListNode(0);
        node.next = head; 
        ListNode pre = node;
        ListNode tail = node; 
        while (head!=null) {
            int cnt = 0;
            while(cnt<k){
                cnt++;
                tail = tail.next;
                if(tail==null) return node.next;
            }
            ListNode nxt = tail.next;
            reverseList(head, tail);
            ListNode tmp = head; 
            head = tail;
            tail = tmp;

            tail.next = nxt;
            pre.next = head;
            pre = tail;
            head = nxt;
        }
        return node.next;
    }
}
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

• 感想：唉，偷懒都是有报应的，平时做反转链表题都懒得思考原地方法，直接用栈暴力过题。然而有一次面试面试官要求写反转链表，不允许使用额外空间，结果头插法都不会，当场写得抓耳挠腮，面完就哭了。痛定思痛吧，以后不会的题，坚决不用敷衍的方式骗自己。

相关题目

• 翻转链表
• k个一组翻转链表