LeetCode.25 Hard k个一组翻转链表

Quistion

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

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

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

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

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

Ideas

定义：

total -> 总节点数
k -> 每组节点书

可以把整个链表的翻转拆分成： total % k 个子链表翻转

翻转完成子链表后，原来的head变成tail，原来的tail变成了head

在进行翻转之前通过两个指针分别标记下一个子链表的head和上一个子链表的tail：

prev -> [a -> b -> c] -> nextHead

只需要:

1. 将prev.next指向新的head，在让prev自己本身指向tail

2. 将head指向nextHead，重新findTail()

就可以翻转每一个子链表

Answer

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1个节点一组的情况直接返回原链表
        if(k == 1) {
            return head;
        }

        // 根据k个一组，检查链表长度是否符合条件
        ListNode tail = findTail(head, k-1);
        // 没找到符合条件的tail则不翻转，直接返回head
        if(tail == null) {
            return head;
        }

        // 虚构头节点start，只用来通过start.next找到整个链表翻转之后的head
        ListNode start = new ListNode(0, head);
        // 虚构头节点prev，用来表示上一个子链表的tail
        ListNode prev = start;

        while(tail != null) {
            // 因为这个时候prev已经有了，所以记录nextHead就行
            ListNode nextHead = tail.next;
            // 翻转，返回新的head和tail
            ListNode[] res = reverse(head, tail, k);
            // prev.next 指向新的head
            prev.next = res[0];
            // tail指向新的tail
            tail = res[1];
            tail.next = nextHead;
            head = nextHead;
            prev = tail;
            // 查找新的tail
            tail = findTail(head, k-1);
        }

        // 最后只需要通过start找到真正的head就行了
        return start.next;
    }

    // 翻转子链表
    public ListNode[] reverse(ListNode head, ListNode tail, int k) {
        // 新的head和tail
        ListNode newHead = tail;
        ListNode newTail = head;

        // 三个连续的指针
        ListNode x = head;
        ListNode y = x.next;
        ListNode z = y.next;
        // 需要翻转的次数
        int re = k-1;

        while(re > 0) {
            // 将y.next指向x就完成了单个节点的翻转
            y.next = x;

            // 将xyz三个指针依次向后移动
            x = y;
            y = z;
            // 因为最外面的循环条件是while(tail != null)，而z相当于tail.next，所以需要单独判断
            if(z != null) {
                z = z.next;
            }
            re--;
        }
        // 返回新的节点
        return new ListNode[]{newHead, newTail};
    }

    public ListNode findTail(ListNode head, int remain) {
        while(remain > 0) {
            if(head == null) {
                return head;
            }
            head = head.next;
            remain--;
        }

        return head;
    }
}

执行结果：

通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.5 MB, 在所有 Java 提交中击败了92.14%的用户