單鏈表反轉(zhuǎn)：

給你單鏈表的頭節(jié)點(diǎn) head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

事例

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

輸入：head = []
輸出：[]

迭代方式實(shí)現(xiàn)：

迭代圖解

//迭代方式實(shí)現(xiàn)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
       ListNode* cur;//當(dāng)前節(jié)點(diǎn)
       ListNode* pre;//上一個(gè)節(jié)點(diǎn)
       ListNode* temp;//臨時(shí)節(jié)點(diǎn)
       while(cur){
           //1.臨時(shí)節(jié)點(diǎn)記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
           temp  = cur.next;
           //2.當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向?yàn)樯弦粋€(gè)節(jié)點(diǎn)
           cur.next = pre;
           //3.當(dāng)前節(jié)點(diǎn)設(shè)置為上個(gè)節(jié)點(diǎn)
           pre = cur;
           //4.當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)
           cur = temp;
       }
       //返回pre節(jié)點(diǎn)，當(dāng)循環(huán)結(jié)束pre節(jié)點(diǎn)就相當(dāng)于當(dāng)前節(jié)點(diǎn)
       return pre
    }
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)O(n)，其中 nn 是鏈表的長度。需要遍歷鏈表一次。

• 空間復(fù)雜度：O(1)O(1)。

遞歸方式實(shí)現(xiàn)：

遞歸圖解

//遞歸方式實(shí)現(xiàn)(理解難度偏高)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //如果為空直接返回
        if(!head||!head.next){
             return head;
        }
        //遞歸調(diào)用，將cur設(shè)置為head的下一個(gè)節(jié)點(diǎn)
        ListNode* cur = reverseList(head.next);
        // head節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)反向指向head節(jié)點(diǎn)，這一句進(jìn)行倒轉(zhuǎn)
        head.next.next = head;
        //將 head節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為空，一遍后續(xù)的遞歸判斷
        head.next = nullptr;
        //返回當(dāng)前節(jié)點(diǎn)
        return cur;
    }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)O(n)，其中 nn 是鏈表的長度。需要對鏈表的每個(gè)節(jié)點(diǎn)進(jìn)行反轉(zhuǎn)操作。

• 空間復(fù)雜度：O(n)O(n)，其中 nn 是鏈表的長度?？臻g復(fù)雜度主要取決于遞歸調(diào)用的?？臻g，最多為 nn 層。

鏈表中環(huán)的檢測和入口節(jié)點(diǎn)尋找：

給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 從鏈表的頭節(jié)點(diǎn)開始沿著 next 指針進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)為環(huán)的入口節(jié)點(diǎn)。如果鏈表無環(huán)，則返回 null。

事例1

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

事例2

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

哈希表方式實(shí)現(xiàn)：

我們遍歷鏈表中的每個(gè)節(jié)點(diǎn)，并將它記錄下來；一旦遇到了此前遍歷過的節(jié)點(diǎn)，就可以判定鏈表中存在環(huán)。借助哈希表可以很方便地實(shí)現(xiàn)。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
         //定義一個(gè)哈希表
        unordered_set<ListNode *> visited;
        while(!head){
            //如果存在該節(jié)點(diǎn)直接返回該節(jié)點(diǎn)
            if(visited.count(head)){
                return head;
            }
            //不存在則加入到表中
            visited.insert(head);
            //設(shè)置下一個(gè)
            head = head->next;
        }
        //沒有則返回空
        return nullptr;
    }
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(N)O(N)，其中 NN 為鏈表中節(jié)點(diǎn)的數(shù)目。我們恰好需要訪問鏈表中的每一個(gè)節(jié)點(diǎn)。

• 空間復(fù)雜度：O(N)O(N)，其中 NN 為鏈表中節(jié)點(diǎn)的數(shù)目。我們需要將鏈表中的每個(gè)節(jié)點(diǎn)都保存在哈希表當(dāng)中。

Java知識(shí)點(diǎn)：如果用Java實(shí)現(xiàn)使用的是HastSet。Set是一個(gè)繼承于Collection的接口，Set是一種不包括重復(fù)元素的Collection。它維持它自己的內(nèi)部排序，所以隨機(jī)訪問沒有任何意義。與List一樣，它同樣運(yùn)行null的存在但是僅有一個(gè)。由于Set接口的特殊性，所有傳入Set集合中的元素都必須不同，關(guān)于API方面。Set的API和Collection完全一樣。實(shí)現(xiàn)了Set接口的集合有：HashSet、TreeSet、LinkedHashSet、EnumSet。
HashSet堪稱查詢速度最快的集合，因?yàn)槠鋬?nèi)部是以HashCode來實(shí)現(xiàn)的。集合元素可以是null,但只能放入一個(gè)null。它內(nèi)部元素的順序是由哈希碼來決定的，所以它不保證set的迭代順序；特別是它不保證該順序恒久不變。需要重寫 hashCode 和 equals 方法。

快慢指針方式實(shí)現(xiàn)：

我們使用兩個(gè)指針，fast 與 slow。它們起始都位于鏈表的頭部。隨后，slow 指針每次向后移動(dòng)一個(gè)位置，而 fast 指針向后移動(dòng)兩個(gè)位置。如果鏈表中存在環(huán)，則 fast 指針最終將再次與 slow 指針在環(huán)中相遇。而相遇后起點(diǎn)到相遇點(diǎn)的距離通過計(jì)算正好等于入環(huán)點(diǎn)到環(huán)入口的距離，所以初始化一個(gè)節(jié)點(diǎn)從頭開始，和slow節(jié)點(diǎn)同步前進(jìn)，相遇的點(diǎn)就是環(huán)入口節(jié)點(diǎn)。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //初始化快慢指針
        ListNode *fast = head;
        ListNode *slow = head;
        //當(dāng) fast 為空停止
        while(fast != nullptr){
          //slow前進(jìn)一步
          slow = slow.next;
          //fast為空直接返回
          if(fast.next = nullptr){
            return nullprt;
          }
          //fast前進(jìn)兩步
          fast = fast.next.next;
          //fast和slow相遇
          if(slow == fast){
           //初始化一個(gè)新的節(jié)點(diǎn)設(shè)置為頭
           ListNode *ptr = head;
           //循環(huán)前進(jìn)直到他們相遇
           while (ptr != slow) {
             ptr = ptr->next;
             slow = slow->next;
           }
           //返回相遇的點(diǎn)，而這個(gè)點(diǎn)就是環(huán)入口點(diǎn)
           return ptr;
          }
        }
        return nullptr;
    }
};

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)O(N)，其中 NN 為鏈表中節(jié)點(diǎn)的數(shù)目。在最初判斷快慢指針是否相遇時(shí)，slow 指針走過的距離不會(huì)超過鏈表的總長度；隨后尋找入環(huán)點(diǎn)時(shí)，走過的距離也不會(huì)超過鏈表的總長度。因此，總的執(zhí)行時(shí)間為 O(N)+O(N)=O(N)O(N)+O(N)=O(N)。

• 空間復(fù)雜度：O(1)O(1)。我們只使用了slow,fast,ptr 三個(gè)指針。

合并兩個(gè)有序鏈表：

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

事例

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

輸入：l1 = [], l2 = []
輸出：[]

輸入：l1 = [], l2 = [0]
輸出：[0]

遞歸方式實(shí)現(xiàn)：

待續(xù)...