LeetCode25-k个一组翻转链表

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/reverse-nodes-in-k-group/

中文链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

题目详述

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

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

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->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
public class LeetCode_00025 {

    // 递归
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int cnt = 0;
        while (cnt < k && cur != null) {
            ++cnt;
            cur = cur.next;
        }
        // 不足 k 个直接返回
        if (cnt < k) {
            return head;
        }
        // 翻转 k 个结点
        cur = head;
        ListNode pre = null;
        for (int i = 0; i < k; ++i) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 递归翻转剩余结点
        head.next = reverseKGroup(cur, k);
        return pre;
    }
}

由于要求只能使用常数的额外空间，故需用迭代法，不过递归更容易理解。

递归版。

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
public class LeetCode_00025 {

    // 迭代
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k == 1) {
            return head;
        }
        // 新建一个哑结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head;
        ListNode pre = dummy;
        int cnt = 0;
        while (cur != null) {
            if (++cnt == k) {
                cnt = 0;
                // 翻转区间 [begin, next)
                ListNode begin = pre.next;
                ListNode next = cur.next;
                pre.next = reverse(begin, next);
                // begin 为翻转后的尾结点，链上后面的结点
                begin.next = next;
                pre = begin;
                cur = next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * 翻转区间 [begin, end) 的链表
     * @param begin 起始结点（包含）
     * @param end 终止结点（不包含）
     * @return 翻转后的头结点
     */
    private ListNode reverse(ListNode begin, ListNode end) {
        ListNode cur = begin;
        ListNode pre = null;
        while (cur != end) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}