前言

又是一波算法題...報告，先申明：我不是要跳槽，也不是在刷算法題。

就是單純最近在看書，翻到了之前買的一些網(wǎng)課，拿出來讀一讀。發(fā)現(xiàn)還是挺有意思的，所以特定記錄一下。

正文

今天的內(nèi)容，還是延續(xù)上一篇隊列的后續(xù)。先來一道基礎(chǔ)題目熱熱身：

反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表這道題應該很多同學都做過，而且也是面試中的?？?，所以直接上答案：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

沒啥特別好說的：兩個變量，一個記錄當前，一個記錄前一個。遍歷鏈表，讓當前的next指向前一個，更新當前 / 前一個 就好了。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

遞歸實現(xiàn)有一個比較棘手的問題需要解決：如何把上一個遞歸棧內(nèi)的節(jié)點指向 反轉(zhuǎn)中鏈表的尾部。這個問題重點在于理解：head.next.next = head; head.next = null;。

這段代碼做了倆件事情：

• 1.反轉(zhuǎn)的兩個鏈節(jié)點
• 2.切斷了head.next

這樣對于上一個遞歸棧內(nèi)的head通過head.next.next = head，``head.next.next`此時為null，因為已經(jīng)被下一個遞歸棧內(nèi)的代碼切斷。此時直接指向自己，就是把自己掛到了已經(jīng)反轉(zhuǎn)好的鏈表上了。

環(huán)形鏈表

image.png

image.png

鏈表中有環(huán)，就意味著某個節(jié)點的next指向了這個節(jié)點的前驅(qū)某個節(jié)點。所以解題思路也就基本有了：遍歷節(jié)點，如果當前節(jié)點在之前遍歷過那么就有環(huán)...

以這個思路單純解決問題，是在是太簡單了。題目中有一個進階部分：空間復雜度O(1)，所以咱們記錄遍歷過的節(jié)點，那就肯定沒辦法O(1)...轉(zhuǎn)念一想也很簡單：咱們上邊的方案是空間換時間，既然空間不允許，那咱們就時間換空間。

思路：一個變量cur記錄當前節(jié)點，一個變量n定為當前.next，負責往后遍歷。n走完一遍，cur往下走，n繼續(xù)遍歷。當n遍歷的過程中發(fā)現(xiàn)和cur相同，那么就有環(huán)。但是這種方案提起來就有點慢..

其實咱們上述的思路都想復雜了。環(huán)形有一個啥特點？兩個速度一樣的單位一定為相交，咱們只需要選取最小的速度差即可，倆個節(jié)點就可以成環(huán)。所以問題就解了...

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

尾聲

其實今天的題目都很基礎(chǔ)，但是為啥還是記錄下來了呢？主要還不是因為自己菜，看完之后覺得“恍然大悟”，所以就把自己思考的過程記了一下。

大家就取其精華去其糟粕吧。與君共勉~