反轉(zhuǎn)鏈表系列問題

作者：Grey

原文地址：

博客園：反轉(zhuǎn)鏈表系列問題

CSDN：反轉(zhuǎn)鏈表系列問題

反轉(zhuǎn)單鏈表

題目描述見：LeetCode 206. Reverse Linked List

思路如下

對于任何一個節(jié)點 cur 來說，記錄一個前驅(qū)節(jié)點 pre (第一個節(jié)點的前驅(qū)節(jié)點是 null )

先用一個臨時節(jié)點 tmp 記錄 cur 的下一個節(jié)點，然后設(shè)置

cur.next = pre;
pre = cur;
cur = tmp;

以下是示例圖

假設(shè)原始鏈表如下

第一個節(jié)點的反轉(zhuǎn)流程如下

第二個節(jié)點的反轉(zhuǎn)流程如下

最后返回 pre 節(jié)點即為反轉(zhuǎn)后的節(jié)點。

代碼如下

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

時間復(fù)雜度\(O(N)\)，空間復(fù)雜度\(O(1)\)。

反轉(zhuǎn)鏈表也可以用遞歸方法來實現(xiàn)

定義遞歸函數(shù) ListNode reverse(ListNode cur)，這個遞歸函數(shù)的含義是

反轉(zhuǎn)以 cur 為頭的鏈表，并把反轉(zhuǎn)后的頭節(jié)點返回。

這個遞歸函數(shù)的 base case 是，只有一個節(jié)點的時候，即

if (cur == null || cur.next == null) {
    return cur;
}

這種情況下，直接返回當(dāng)前節(jié)點即可。

接下來是普遍情況：

當(dāng)前來到 cur 節(jié)點，c，d，e 已經(jīng)完成了反轉(zhuǎn)。

此時 cur 需要做如下操作：把 c , d, e 反轉(zhuǎn)后的頭節(jié)點獲取到，假設(shè)為 pre ， 在上圖中，pre 就是 e 節(jié)點，然后 cur 再做如下操作

cur.next.next = cur;
cur.next = null;

其中cur.next = null非常重要，只有這樣，才能防止出現(xiàn)環(huán)。完整代碼如下

class Solution {
    public ListNode reverseList(ListNode cur) {
        return reverse(cur);
    }

    // 反轉(zhuǎn)cur為頭的鏈表，并把反轉(zhuǎn)后的頭節(jié)點返回
    public ListNode reverse(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        ListNode pre = reverse(cur.next);
        cur.next.next = cur;
        cur.next = null;
        return pre;
    }
}

時間復(fù)雜度\(O(N)\)

空間復(fù)雜度\(O(N)\)(遞歸棧占用的空間)

反轉(zhuǎn)雙向鏈表

雙向鏈表和單鏈表的反轉(zhuǎn)類似，每個節(jié)點要多處理一次每個節(jié)點的前驅(qū)指針，

完整代碼如下

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        DoubleNode pre = null;
        DoubleNode cur = head;
        while (cur != null) {
            DoubleNode tmp = cur.next;
            cur.next = pre;
            cur.last = tmp;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

反轉(zhuǎn)單鏈表一部分

題目描述見：LeetCode 92. Reverse Linked List II

本題核心依然是反轉(zhuǎn)鏈表，只是增加了一些變量來記錄需要反轉(zhuǎn)鏈表的頭位置和結(jié)尾位置，不過需要注意的是，本題的鏈表開始位置是從 1 開始，所以，如果m = 1 && n != 1，說明反轉(zhuǎn)鏈表后需要返回新的頭部，只要m > 1，反轉(zhuǎn)鏈表一部分以后，返回原先的頭即可。

此外，本題的 follow up 提到

Follow up: Could you do it in one pass?

就是遍歷一次鏈表能否解決問題，具體代碼如下

class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head.next == null || left == right) {
            // 只有一個節(jié)點，怎么反轉(zhuǎn)都一樣
            // 只要反轉(zhuǎn)一個節(jié)點，反轉(zhuǎn)前后鏈表還是一樣的
            return head;
        }
        if (left == 1) {
            // 需要換頭
            ListNode pre = null;
            ListNode end = head;
            ListNode cur = head;
            int gap = right - left + 1;
            while (gap != 0) {
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
                gap--;
            }
            end.next = cur;
            return pre;
        } else {
            ListNode pre = null;
            for (int i = 1; i < left; i++) {
                pre = pre == null ? head : pre.next;
            }
            ListNode end = pre;
            ListNode cur = pre == null ? head : pre.next;
            ListNode last = cur;
            int gap = right - left + 1;
            while (gap != 0) {
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
                gap--;
            }

            if (end != null) end.next = pre;
            if (last != null) last.next = cur;
            // 不需要換頭，返回原先的頭節(jié)點
            return head;
        }
    }
}

更多

算法和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記

算法和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)代碼

參考資料

算法和數(shù)據(jù)結(jié)構(gòu)體系班-左程云

總結(jié)

以上是生活随笔為你收集整理的反转链表系列问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。