2021/3/19 链表中的节点每k个一组翻转

题目描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 O(1)
例如：
给定的链表是1→2→3→4→5
对于 k=2, 你应该返回 2→1→4→3→5
对于 k=3, 你应该返回 3→2→1→4→5

示例1

输入

{1,2,3,4,5},2

返回值

{2,1,4,3,5}

解题思路

使用递归法，去解决每 k 个部分的反转。

从上面图例可以看出，每次反转结束之后，pre 指向的位置是上一次反转结束时最后一个元素的下一个元素（即 1 连接着 4）。我们可以利用这一点做一个递归。

Java代码实现

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        if (head == null || k <= 1) return head;
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        // 遍历链表，如果遍历到 null，说明长度不够，返回 head 即可
        for (int i = 0; i < k; ++i) {
            if (cur == null) return head;
            cur = cur.next;
        }
        cur = head;    // 重新设置回头部
        // 从 head 开始到后面 k 个元素的链表反转操作
        for (int i = 0; i < k; ++i) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        // head.next 就是下一次反转的 prev
        head.next = reverseKGroup(next, k);
        return prev;
    }
}