鏈表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)\)。

更多

算法和數據結構學習筆記

算法和數據結構學習代碼

參考資料

算法和數據結構體系班-左程云

總結

以上是生活随笔為你收集整理的链表K个节点的组内逆序调整问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。