当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表

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


上一篇 LeetCode.210.Course Schedule II 课程表 II

下一篇 LeetCode.560.Subarray Sum Equals K 和为K的子数组

阅读
评论
628
阅读预计3分钟
创建日期 2020-05-16
修改日期 2020-05-16
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论