leetcode.Q25.k个一组翻转链表

解析思路

leetcode 困难，题目描述点击这里。

本题属于链表翻转的进阶题，思路如下：

  1. 添加一个虚拟节点头，方便编码编写
  2. 遍历链表，当遍历到k个时，对这k个进行处理，处理过程如下：
    1. 对这k个节点进行翻转
    2. 翻转后处理头尾节点的关系，注意需要记录头节点、头节点之前的一个节点、尾节点和尾节点的下一节点共四个节点，细节看代码
  3. 一轮处理完毕后继续遍历，当遍历到k个时继续第2步，直到结束遍历

代码

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
public class Q25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode res = new ListNode(), index = head;
        res.next = head;
        int count = 0;
        //left:开始翻转节点的父节点
        //right:结束翻转的节点
        ListNode beforeL = res, l = beforeL.next, r, afterR;
        while (index != null) {
            if (++count == k) {
                //进行翻转
                r = index;
                afterR = index.next;
                reverse(l, count);
                index = l;
                //处理头尾节点关系
                l.next = afterR;
                beforeL.next = r;
                //进行下一轮循环
                beforeL = index;
                l = index.next;
                count = 0;
            }
            index = index.next;
        }
        return res.next;
    }

    /**
     * 翻转start后的n个节点
     *
     * @param start
     * @param n
     */
    private void reverse(ListNode start, int n) {
        //反转节点
        ListNode prev = null;
        for (int i = 0; i < n; i++) {
            ListNode next = start.next;
            start.next = prev;
            prev = start;
            start = next;
        }
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        new Q25().reverseKGroup(node, 3);
    }
}

本文原创发布于:https://blog.fleyx.com,转载请注明出处
如果本篇文章对您有帮助欢迎打赏哦！
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号