链表K个节点的组内逆序调整问题

作者：Grey

原文地址：

博客园：链表K个节点的组内逆序调整问题

CSDN：链表K个节点的组内逆序调整问题

题目描述

LeetCode 25. Reverse Nodes in k-Group

本题的 follow up 是：

Follow-up: Can you solve the problem in O(1) extra memory space?

即用(O(1))的空间复杂度实现整个算法。

主要思路

本题需要设计两个方法：

第一个方法

ListNode getKGroupEnd(ListNode start, int k)

该方法表示：从链表start位置开始，数够k个位置，返回k个位置后的那个节点。

比如链表为：

...-> start -> b -> c -> d -> e

假设：k = 3，

则：表示从start开始，数够 3 个，所以返回c节点

如果是下述情况

...-> start -> b -> c -> null

假设：k = 6，

由于start后面不够 6 个节点，所以返回null，完整代码如下：

public static ListNode getKGroupEnd(ListNode start, int k) {
    while (--k != 0 && start != null) {
        start = start.next;
    }
    return start;
}

第二个方法void reverse(ListNode start, ListNode end)，表示反转start到end之间的链表。

例如：原链表为：

....->a->b->c->d->e....

假设：start = a, end = d

经过reverse方法，会变成

...d->c->b->a->e.....

reverse方法也相对比较简单，就是链表反转的一种特殊情况，实现代码如下:

public static void reverse(ListNode start, ListNode end) {
    end = end.next;
    ListNode pre = null;
    ListNode cur = start;
    while (cur != end) {
        ListNode tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    start.next = end;
}

有了上述两个方法，我们可以比较方便实现原题要求，主流程如下

public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode start = head;
    ListNode end = getKGroupEnd(start, k);
    if (end == null) {
        return head;
    }
    // 第一组凑齐了！
    head = end;
    reverse(start, end);
    // 上一组的结尾节点
    ListNode lastEnd = start;
    while (lastEnd.next != null) {
        start = lastEnd.next;
        end = getKGroupEnd(start, k);
        if (end == null) {
            return head;
        }
        reverse(start, end);
 服务器托管网       lastEnd.next = end;
        lastEnd = start;
    }
    return head;
}

整个过程时间复杂度(O(N))，空间复杂度(O(1))。

更多

算法和数据结构学习笔记

算法服务器托管网和数据结构学习代码

参考资料

算法和数据结构体系班-左程云

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Rainbond助力“信创应用”迁移上云

Rainbond v5.14.2 版本，又称信创版本。从这个版本开始，开源用户也可以利用 Rainbond 管理符合信创要求的硬件计算资源。在这个版本中，产品团队将此前只在企业版产品中存在的信创相关功能拆分出来，融入到了开源产品路线之中。本文围绕如何在信创环境…