是熊是猫溜溜

子非鱼，焉知鱼之乐

leetcode-25 K个一组翻转链表

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你可以设计一个只使用常数额外空间的算法来解决此问题吗？你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

原题介绍

示例一

digraph leetcode_92_1 { 
bgcolor="#f7f7f7"

rankdir=LR
subgraph cluster_name {
    
    subgraph cluster_1 {
        n0 [label="1" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        n1 [label="2" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        n2 [label="3" shape=circle,color=yellow,fillcolor=lightyellow,style=filled]
        n3 [label="4" shape=circle,color=yellow,fillcolor=lightyellow,style=filled]
        n4 [label="5" shape=circle,color=black,fillcolor=white,style=filled]
        rank=same;
        n0 -> n1 -> n2 -> n3 -> n4 
        style=invis
    }

    subgraph cluster_2 {
        r0 [label="2" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        r1 [label="1" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        r2 [label="4" shape=circle,color=yellow,fillcolor=lightyellow,style=filled]
        r3 [label="3" shape=circle,color=yellow,fillcolor=lightyellow,style=filled]
        r4 [label="5" shape=circle,color=black,fillcolor=white,style=filled]

        rank=same;
        r0 -> r1 -> r2 -> r3 -> r4 
        style=invis
    }    

    n2 -> r2[constraint=false,color="red",pad=30]    

}

label=<<B>图 1.1 示例一</B>>

}

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

代码实现

递归实现

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
public class Solution {
    private ListNode nextNode;

    public ListNode reverseKGroup(ListNode head, int k) {
        //1. 判空
        if (head == null || head.next == null || k == 1) {
            return head;
        }

        //2. 遍历计算链表长度
        int len = 1;
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
            len++;
        }

        //3. 每组k各元素，计算分组数
        int group = len / k;

        //4. 分别处理每个组，分别进行反转
        ListNode newHead = null;
        for (int idx = 1; idx <= group; idx++) {
            newHead = reverseBetween(head, k * (idx - 1) + 1, k * idx);
            head = newHead;
        }
        return head;
    }

    /**
     * 反转链表区间
     *
     * @param head 链表头
     * @param left 区间左
     * @param right 区间右
     * @return 新链表节点
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || right == 1) {
            return head;
        }
        if (left > 1) {
            head.next = reverseBetween(head.next, left - 1, right - 1);
            return head;
        }
        return reverse(head, right);
    }

    /**
     * 反转链表前right个节点
     *
     * @param head  链表头
     * @param right 前right个节点
     * @return 新链表头
     */
    public ListNode reverse(ListNode head, int right) {
        if (head.next == null || right == 1) {
            nextNode = head.next;
            return head;
        }
        ListNode newHead = reverse(head.next, right - 1);
        head.next.next = head;
        head.next = nextNode;
        return newHead;
    }
}