LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表

题目描述

25 Reverse Nodes in k-Group
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

Note:
Only constant extra memory is allowed.
You may not alter the values in the list’s nodes, only nodes itself may be changed.

---

相似题目

LeetCode.206.Reverse Linked List 反转链表
LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点
LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表

---

解题过程

1、用一个不存储数据的 dumbHead 头结点作为新链表的头结点，可以简化操作，避免第一个结点特例的判断，最后返回 dumbHead.next 即可。
2、lastEnd 记录上一段的终点， nextFirst 记录下一段的起点，每次向前走 k-1 步，然后停住，对当前段内的 k-1 个结点依次使用头插法插入到 lastEnd 之后，然后重置计数器继续从 nextFirst 向后遍历。
3、当前段内进行头插完毕后，还需要将当前段的最后一个结点的 next 指向下一段的第一个结点 nextFirst 方能将链表连上。如何知道当前段头插完毕后的最后一个结点呢？其实当前段头插完毕后的最后一个结就是开始时 lastEnd 的 next 结点。

时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV202005 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (null == head || head.next == null || k < 2) {
            return head;
        }
        ListNode dumbHead = new ListNode(0);
        dumbHead.next = head;
        // lastEnd 上一段的终点， nextFirst 下一段的起点
        ListNode lastEnd = dumbHead, nextFirst;
        ListNode cur = head;
        int count = 1;
        while (cur != null) {
            if (count < k) {
                // 向前走 k-1 步
                cur = cur.next;
                count++;
            } else {
                // 记住下一段的起点
                nextFirst = cur.next;
                // 记住当前段的起点，逆置完之后就是当前段的终点
                ListNode curEnd = lastEnd.next;
                // 头插法依次将本段的 k-1 个结点插入到 lastEnd 之后
                ListNode p = lastEnd.next.next;
                for (int i = 0; i < k - 1; i++) {
                    ListNode next = p.next;
                    p.next = lastEnd.next;
                    lastEnd.next = p;
                    p = next;
                }
                // 当前段的终点指向下一段的起点
                curEnd.next = nextFirst;
                // 记住上一段的终点
                lastEnd = curEnd;
                // cur 指针归位
                cur = nextFirst;
                // 重新开始计数
                count = 1;
            }
        }
        return dumbHead.next;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_025_ReverseNodesInKGroup.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_025_ReverseNodesInKGroup.java

---