分門別類刷演算法，堅持，進步！

刷題路線參考：https://github.com/youngyangyang04/leetcode-master

??????https://github.com/chefyuan/algorithm-base

LeetCode通關：鏈表

鏈表基礎

在開始刷題之前，我們最好先了解一下鏈表的一些基礎知識，那么現在，我們開始吧，

鏈表是一種鏈式存盤的線性表，不要求邏輯上相鄰的資料元素在物理位置上也相鄰，

單鏈表

一個單向鏈表包含兩個值: 當前節點的值和一個指向下一個節點的參考，也可以稱之為資料域和指標域，

入口節點稱為頭結點，最后一個節點指向null，

如圖所示：

單鏈表

雙鏈表

雙鏈表，顧名思義，是有兩個方向的鏈表，

每個節點除了有指向下一個節點的參考，還有指向上一個節點的參考，

雙鏈表除了可以從前往后遍歷，還可以從后往前遍歷，

雙向鏈表

回圈鏈表

回圈鏈表，就是最后一個節點的后繼指向頭結點，頭節點的前驅指向最后一個節點，

回圈鏈表

鏈表的存盤方式

我們知道鏈表在記憶體中不是連續分配的，鏈表是通過指標域的指標鏈接記憶體中的各個節點，

所以鏈表在記憶體中是散亂分布在記憶體中的某地址上，分配機制取決于作業系統的記憶體管理，

鏈表記憶體分配

鏈表的定義

鏈表的定義主要包含兩個部分：資料域和指標域，

在Java中因為屏蔽了指標的存在，我們的定義可以是資料，后繼/前驅節點，

單鏈表：

 public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

雙鏈表：

 public class ListNode {
      int val;
      ListNode prev;
      ListNode next;
      ListNode(int x) { val = x; }
  }

鏈表基本操作

我們以單鏈表為例，來看一下鏈表的一些基本操作：

洗掉節點

鏈表洗掉節點

插入節點

插入節點

圖中的插入和洗掉的時間復雜度都為O(1)，但是需要注意，這里的情況是插入和洗掉已經知道前趨節點的情況，

如果，還需要檢索相應的節點，那么時間復雜度是O(n)，

鏈表操作

LeetCode203. 移除鏈表元素

? 題目：203. 移除鏈表元素 (https://leetcode-cn.com/problems/remove-linked-list-elements/)

? 難度：簡單

📕 描述：給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，

題目示例

💡 思路：

洗掉鏈表節點，需要分為兩種情況：

洗掉節點是頭結點：我們將頭結點指向頭結點的下一個節點

頭結點

洗掉節點是非頭結點：我們需要將當前節點的前一個節點指向當前節點的下一個節點

非頭結點

我們來看一下代碼實作：

   /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 203. 移除鏈表元素
     * @author 三分惡
     * @date 2021/7/25 10:08
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode prev = head;
        while (cur != null) {
            ListNode temp = cur.next;
            //洗掉節點
            if (cur.val == val) {
                //頭節點
                if (cur == head) {
                    head = temp;
                }
                //非頭節點
                if (cur != head) {
                    prev.next = cur.next;
                }
            } else {
                prev = cur;
            }
            cur = temp;
        }
        return head;
    }

? 時間復雜度：O(n)，

🏠 空間復雜度：O(1)，

這道題，還有一個更巧妙一點的做法，就是虛擬頭指標——虛擬頭指標是鏈表演算法題中非常好用的一個技巧，

💡 思路：

可以設定一個虛擬的頭指標，讓它的next指向頭節點，這樣頭節點的洗掉就和普通節點是一致的了，

虛擬頭指標

代碼如下：

    /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 203. 移除鏈表元素
     * @author 三分惡
     * @date 2021/7/25 10:08
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        //虛擬頭節點
        ListNode dummy = new ListNode(-1, head);
        ListNode prev = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

🚗 時間復雜度：O(n)，

🏠 空間復雜度：O(1)，

LeetCode707. 設計鏈表

? 題目：707. 設計鏈表 (https://leetcode-cn.com/problems/design-linked-list/)

? 難度：中等

📕 描述：設計鏈表的實作，您可以選擇使用單鏈表或雙鏈表，單鏈表中的節點應該具有兩個屬性：val 和 next，val 是當前節點的值，next 是指向下一個節點的指標/參考，如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節點，假設鏈表中的所有節點都是 0-index 的，

在鏈表類中實作這些功能：

get(index)：獲取鏈表中第 index 個節點的值，如果索引無效，則回傳-1，
addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節點，插入后，新節點將成為鏈表的第一個節點
addAtTail(val)：將值為 val 的節點追加到鏈表的最后一個元素，
addAtIndex(index,val)：在鏈表中的第 index 個節點之前添加值為 val 的節點，如果 index 等于鏈表的長度，則該節點將附加到鏈表的末尾，如果 index 大于鏈表長度，則不會插入節點，如果index小于0，則在頭部插入節點，
deleteAtIndex(index)：如果索引 index 有效，則洗掉鏈表中的第 index 個節點，

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //鏈表變為1-> 2-> 3
linkedList.get(1);            //回傳2
linkedList.deleteAtIndex(1);  //現在鏈表是1-> 3
linkedList.get(1);            //回傳3

提示：

所有val值都在 [1, 1000] 之內，
操作次數將在 [1, 1000] 之內，
請不要使用內置的 LinkedList 庫，

💡 思路：

這是一道大題，

鏈表基本操作的圖示在前面已經給出了，

比較簡練的方式是設定一個偽頭節點，保證鏈表永不為空，這樣操作起來會方便很多，

但是，我本人看過一點Java鏈表的代碼，所以不想采用這種方式，

PS：這里踩了一個坑，沒仔細審題，鏈表index是從0開始的，導致思考5分鐘，AC兩小時，

好了，我們直接看代碼：

/**
 * @Author: 三分惡
 * @Date: 2021/7/25
 * @Description: 707. 設計鏈表
 * https://leetcode-cn.com/problems/design-linked-list/
 * <p>
 * 鏈表界節點是 0——index
 **/

public class MyLinkedList {

    //鏈表元素的個數
    int size;
    //頭結點
    ListNode head;


    /**
     * 初始化鏈表
     */
    public MyLinkedList() {
        size = 0;
    }

    /**
     * 獲取第index個節點的數值
     */
    public int get(int index) {
        //非法引數
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    /**
     * 在鏈表最前面插入一個節點
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /**
     * 在鏈表的最后插入一個節點
     */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /**
     * 在第 index 個節點之前插入一個新節點，例如index為0，那么新插入的節點為鏈表的新頭節點，
     * 如果 index 等于鏈表的長度，則說明是新插入的節點為鏈表的尾結點
     * 如果 index 大于鏈表的長度，則回傳空
     */
    public void addAtIndex(int index, int val) {
        //非法引數
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        //如果鏈表為空，直接作為頭節點
        if (size == 0) {
            head = new ListNode(val);
            size++;
            return;
        }
        //插入
        size++;
        ListNode addNode = new ListNode(val);
        //插入頭節點之前
        if (index == 0) {
            addNode.next = head;
            head = addNode;
            return;
        }
        //找到前驅節點
        ListNode pre = head;
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        addNode.next = pre.next;
        pre.next = addNode;
    }

    /**
     * 洗掉第index個節點
     */
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size-1) {
            return;
        }
        size--;
        //頭節點
        if (index == 0) {
            head = head.next;
            return;
        }
        //非頭節點
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        //洗掉節點
        prev.next = prev.next.next;
    }
}

?時間復雜度：

addAtHead： O(1)
addAtInder，get，deleteAtIndex: O(n)，
addAtTail：O(n)，

🏠空間復雜度：所有的操作都是 O(1)，

虛擬頭指標，以及雙鏈表的實作，這里就留個白了，

雙指標解決的題目

劍指 Offer 22. 鏈表中倒數第k個節點

? 題目：劍指 Offer 22. 鏈表中倒數第k個節點 (https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

? 難度：簡單

📕 描述：輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，

例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6，這個鏈表的倒數第 3 個節點是值為 4 的節點，

題目示例

💡 思路：

這道題可以用雙指標的辦法，

以示例說明，一個指標pre在前，先跑1步，一個指標after在后，跟著跑，pre到頭的時候，剛好afer是倒數第二個，

倒數第k個節點

代碼實作：

    /**
     * 劍指 Offer 22. 鏈表中倒數第k個節點
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode preNode = head, afterNode = head;
        int step = 0;
        while (preNode!=null) {
            preNode = preNode.next;
            step++;
            if (step > k) {
                afterNode = afterNode.next;
            }
        }
        return afterNode;
    }

? 時間復雜度：O(n)，

LeetCode876. 鏈表的中間結點

? 題目：876. 鏈表的中間結點 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)

? 難度：簡單

📕 描述：給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，

如果有兩個中間結點，則回傳第二個中間結點，

💡 思路：

和上一道題有點類似，

上一道題是兩個指標分先、后，

這道題可以兩個指標分快、慢，

一示例1為例，fast指標跑兩步，slow指標跑一步，fast指標恰好跑的是slow的兩倍，fast指標跑到頭了，slow指標不就恰好跑到中間了嘛！

鏈表的中間節點

代碼如下：

    /**
     * 876. 鏈表的中間結點
     *
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        //定義快慢指標
        ListNode fastNode = head, slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            //快指標走兩步
            fastNode = fastNode.next.next;
            //慢指標走一步
            slowNode = slowNode.next;
        }
        return slowNode;
    }

? 時間復雜度：O(n)，

LeetCode19. 洗掉鏈表的倒數第 N 個結點

? 題目：19. 洗掉鏈表的倒數第 N 個結點 (https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)

? 難度：中等

📕 描述：給你一個鏈表，洗掉鏈表的倒數第 n 個結點，并且回傳鏈表的頭結點，

**進階：**你能嘗試使用一趟掃描實作嗎？

題目示例

💡 思路：

這道題上手是不是就覺得很熟？

這是 203.移除鏈表元素 和 劍指 Offer 22. 鏈表中倒數第k個節點的結合，

那么解法，我們同樣可以結合這兩道題，

快慢指標找到倒數第N個節點
虛擬頭指標輔助洗掉

洗掉倒數第N個節點

代碼如下：

  /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 19. 洗掉鏈表的倒數第 N 個結點
     * @author 三分惡
     * @date 2021/7/25 17:17
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        //快慢指標
        ListNode fast = head, slow = head;
        //虛擬頭節點
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //一個指標從虛擬頭節點開始跑
        ListNode preSlow = dummy;
        //計算步數
        int step = 0;
        while (fast != null) {
            //fast先走n步
            fast = fast.next;
            step++;
            //slow開始移動
            if (step > n) {
                slow = slow.next;
                preSlow = preSlow.next;
            }
        }
        //找到倒數第n個節點，和它的前驅
        preSlow.next = slow.next;
        return dummy.next;
    }

? 時間復雜度：O(n)，

劍指 Offer 52. 兩個鏈表的第一個公共節點

? 題目：876. 鏈表的中間結點 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)

? 難度：簡單

📕 描述：給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，

如果有兩個中間結點，則回傳第二個中間結點，

題目示例

💡 思路：

他們都說這道題浪漫，我卻不想聽什么狗屁的浪漫愛情故事，我只想搞錢，

這道題可以用雙指標解決，定義兩個指標，當某一指標遍歷完鏈表之后，然后掉頭去另一個鏈表的頭部，繼續遍歷，因為速度相同所以他們第二次遍歷的時候肯定會相遇，

如圖（來自參考[3]）：

圖片來自參考[3]

代碼實作：

    /**
     * 劍指 Offer 52. 兩個鏈表的第一個公共節點
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        //定義兩個節點
        ListNode nodeA = headA, nodeB = headB;
        while (nodeA != nodeB) {
            //沒到頭就后移，到頭，就指向另一樹頭結點
            if (nodeA != null) {
                nodeA = nodeA.next;
            } else {
                nodeA = headB;
            }
            //另一個節點也一樣
            if (nodeB != null) {
                nodeB = nodeB.next;
            } else {
                nodeB = headA;
            }
        }
        return nodeA;
    }

? 時間復雜度：O(m+n)，m和n分別為兩個鏈表的長度，

160. 相交鏈表、面試題 02.07. 鏈表相交和這道題基本是一模一樣的，

LeetCode206. 反轉鏈表

? 題目：206. 反轉鏈表 (https://leetcode-cn.com/problems/reverse-linked-list/)

? 難度：簡單

📕 描述：給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

題目示例

💡 思路：

這是一道非常經典的題目，翻轉怎么做呢？

遍歷鏈表，將當前節點的后繼指向當前，

反轉鏈表

在這里我們要額外引入兩個指標：

一個prev表示前趨，用于反轉時候后繼的指向，
一個temp用于臨時存盤下一個節點，這個temp是用來干什么的？用來遍歷，因為反轉之后，原來的next節點已經指向prev了，

說真的，作為一個C語言菜雞，我又想起了被指標陣列、陣列指標支配的日子，所以我畫了一個作為Java程式員理解的示意圖，如有不當之處，請指出，

反轉鏈表

也找到了一張動圖（參考[1])：

在這里插入圖片描述

代碼如下：

    /**
     * 206. 反轉鏈表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            //保存下一個節點
            ListNode temp = current.next;
            //修改當前節點后繼指向
            current.next = prev;
            //修改前趨節點
            prev = current;
            current = temp;
        }
        return prev;
    }

? 時間復雜度：O(n)，

LeetCode92. 反轉鏈表 II

? 題目：92. 反轉鏈表 II (https://leetcode-cn.com/problems/reverse-linked-list-ii/)

? 難度：中等

📕 描述：給你單鏈表的頭指標 head 和兩個整數 left 和 right ，其中 left <= right ，請你反轉從位置 left 到位置 right 的鏈表節點，回傳反轉后的鏈表，

題目示例

💡 思路：

反轉鏈表經常容易忘，我們再做一道進階的題目來鞏固一下，

這道題什么思路呢？

我們可以把反轉的這一部分拆出來，作為新的鏈表，反轉新鏈表，然后再和前后的節點重新連接，

反轉鏈表-II

代碼實作：

   /**
     * @return ListNode
     * @Description: 92. 反轉鏈表 II
     * @author 三分惡
     * @date 2021/7/24 0:32
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //虛擬頭節點
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        //一、獲取被截取的子鏈表的前、后節點
        //移動到左節點前一個節點
        int i = 0;
        for (; i < left - 1; i++) {
            cur = cur.next;
        }
        //保存左節點的前一個節點
        ListNode leftPre = cur;
        //移動到right節點
        for (; i < right; i++) {
            cur = cur.next;
        }
        //保存右節點的后一個節點
        ListNode rightAfter = cur.next;
        //二、截取子鏈表
        //切斷右節點后的部分
        cur.next = null;
        //左節點作為子鏈表頭節點
        ListNode sonHead = leftPre.next;
        //切斷左節點前的部分
        leftPre.next = null;
        //三、反轉子鏈表
        ListNode rNode = reverseList(sonHead);
        //四：重新連接
        leftPre.next = rNode;
        sonHead.next = rightAfter;
        return dummy.next;
    }

    /**
     * @return ListNode
     * @Description: 反轉鏈表
     * @author 三分惡
     * @date 2021/7/25 10:06
     */
    ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

? 時間復雜度：O(n)，

LeetCode234. 回文鏈表

? 題目：234. 回文鏈表(https://leetcode-cn.com/problems/palindrome-linked-list/)

? 難度：簡單

📕 描述：請判斷一個鏈表是否為回文鏈表，

題目示例

💡 思路：

要是雙向鏈表就好了，直接一個指標從頭到尾，一個指標從尾到頭，但是這是一個單鏈表，

所以我們可以用一個串列先把之給存起來，再用雙指標分別從兩頭遍歷比較，

代碼如下：

    /**
     * 234. 回文鏈表
     * 將值復制到集合
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        List<Integer> nodes = new ArrayList<>(16);
        //將鏈表的值放入集合
        while (head != null) {
            nodes.add(head.val);
            head = head.next;
        }
        //雙向遍歷集合
        int start = 0, end = nodes.size() - 1;
        while (start < end) {
            if (!nodes.get(start).equals(nodes.get(end))) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

? 時間復雜度：O(n)，其中 n 指的是鏈表的元素個數，，

🏠 空間復雜度：O(n)，其中 n 指的是鏈表的元素個數，因為我們用了一個ArrayList來存盤資料，

但是題目里還提出了一個進階：

你能否用 O(n) 時間復雜度和 O(1) 空間復雜度解決此題？

既然空間復雜度O(1)，那么就不能引入新的存盤結構，

還是上面那句話，要是雙向鏈表就好了，我們就雙向比較，

所以，考慮一下，我們可以把鏈表的后半段翻轉一下，然后再比較，

回文鏈表

為了完成這個目的，大概需要分三步：

找到中間結點
翻轉鏈表后半段
前半段和后半段比較

所以這種做法就是 876. 鏈表的中間結點 和 206. 反轉鏈表 的組合，

代碼實作如下：

    /**
     * 234. 回文鏈表
     * 快慢指標法
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        //找到中間節點
        ListNode midNode = findMid(head);
        //翻轉鏈表
        ListNode tailHead = reverseList(midNode);
        //比較
        while (tailHead != null) {
            if (head.val != tailHead.val) {
                return false;
            }
            head = head.next;
            tailHead = tailHead.next;
        }
        return true;
    }

    /**
     * 找到中間節點
     *
     * @param head
     * @return
     */
    ListNode findMid(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 翻轉鏈表
     *
     * @param head
     * @return
     */
    ListNode reverseList(ListNode head) {
        ListNode current = head;
        ListNode prev = null;
        while (current != null) {
            //保存下一個節點
            ListNode temp = current.next;
            //修改當前節點后繼指向
            current.next = prev;
            //修改前趨節點
            prev = current;
            current = temp;
        }
        return prev;
    }

? 時間復雜度：O(n)，

🏠 空間復雜度：O(1)，

LeetCode141. 環形鏈表

? 題目：141. 環形鏈表 (https://leetcode-cn.com/problems/linked-list-cycle/)

? 難度：簡單

📕 描述：

給定一個鏈表，判斷鏈表中是否有環，

如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環，為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始），如果 pos 是 -1，則在該鏈表中沒有環，注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，

如果鏈表中存在環，則回傳 true ，否則，回傳 false ，

💡 思路：

這道題是經典的快慢指標，一個指標跑的塊，一個指標跑的慢，如果鏈表成環的話，慢指標一定會追上快指標，

幻形鏈表

代碼如下：

    /**
     * @return boolean
     * @Description: 141. 環形鏈表
     * @author 三分惡
     * @date 2021/7/25 20:16
     */
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        //定義快慢指標
        ListNode fast = head, slow = head;
        //遍歷鏈表
        while (fast != null && fast.next != null) {
            //快指標移動兩步
            fast = fast.next.next;
            //慢指標移動一步
            slow = slow.next;
            //快、慢指標相遇
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

? 時間復雜度：O(n)，

LeetCode142. 環形鏈表 II

? 題目：142. 環形鏈表 II (https://leetcode-cn.com/problems/linked-list-cycle-ii/)

? 難度：中等

📕 描述：

給定一個鏈表，回傳鏈表開始入環的第一個節點，如果鏈表無環，則回傳 null，

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始），如果 pos 是 -1，則在該鏈表中沒有環，注意，pos 僅僅是用于標識環的情況，并不會作為引數傳遞到函式中，

說明：不允許修改給定的鏈表，

進階：

你是否可以使用 O(1) 空間解決此題？

題目示例

💡 思路：

這道題，乍一看，是 141. 環形鏈表 的進階，仔細一看，沒那么簡單，

141. 環形鏈表快指標只管追慢指標，不管在哪追上就行，但這個不行，我們要回傳追上的節點，

怎么辦？

我們可以用一個集合把鏈表節點存進去，要是成環的話，放入的節點肯定會有重復的，

這個集合用什么呢？用HashSet比較合適，

    /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 142. 環形鏈表 II
     * @author 三分惡
     * @date 2021/7/25 20:40
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        HashSet<ListNode> set = new HashSet<>(16);
        while (head != null) {
            //判斷set中是否包含當前元素
            if (set.contains(head)) {
                return head;
            }
            //添加元素
            set.add(head);
            //繼續迭代
            head = head.next;
        }
        return null;
    }

? 時間復雜度：O(n)，

🏠 空間復雜度：O(n)，

我們看到進階里提到了空間復雜度O(1)，這就涉及到非常巧妙的一個雙指標做法，

下圖是一種比較典型的情況下，做的推導[4]：

雙指標法環形鏈表 [4]

代碼實作：

    /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 142. 環形鏈表 II
     * @author 三分惡
     * @date 2021/7/25 20:52
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        //定義快、慢指標
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //快慢指標相遇
            if (fast == slow) {
                //快指標重回head
                fast = head;
                while (slow != fast) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }

? 時間復雜度：O(n)，

🏠 空間復雜度：O(1)，

雙鏈表問題

LeetCode86. 分隔鏈表

? 題目：86. 分隔鏈表 (https://leetcode-cn.com/problems/partition-list/)

? 難度：中等

📕 描述：

給你一個鏈表的頭節點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有小于 x 的節點都出現在大于或等于 x 的節點之前，

你應當保留兩個磁區中每個節點的初始相對位置，

💡 思路：

可以創建兩個鏈表，一個鏈表存小節點，一個鏈表存大節點，最后再把兩個鏈表合并起來，

代碼如下：

    /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 86. 分隔鏈表
     * @author 三分惡
     * @date 2021/7/25 21:58
     */
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        //定義兩個新鏈表
        ListNode small = new ListNode(-1);
        ListNode big = new ListNode(-1);
        //小、大鏈表頭節點
        ListNode smallHad = small;
        ListNode bigHead = big;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                //小鏈表插入節點
                small.next = cur;
                small = small.next;
            } else {
                //大鏈表插入節點
                big.next = cur;
                big = big.next;
            }
            cur = cur.next;
        }
        //防止成環
        big.next = null;
        //合并鏈表
        small.next = bigHead.next;
        return smallHad.next;
    }

? 時間復雜度：O(n)，

LeetCode328. 奇偶鏈表

? 題目：328. 奇偶鏈表 (https://leetcode-cn.com/problems/odd-even-linked-list/)

? 難度：中等

📕 描述：

給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起，請注意，這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性，

請嘗試使用原地演算法完成，你的演算法的空間復雜度應為 O(1)，時間復雜度應為 O(nodes)，nodes 為節點總數，

示例 1:

輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL

示例 2:

輸入: 2->1->3->5->6->4->7->NULL 
輸出: 2->3->6->7->1->5->4->NULL

說明:

應當保持奇數節點和偶數節點的相對順序，
鏈表的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推，

💡 思路：

和上道題類似，我們也是將新建兩個鏈表，分別保存奇、偶數位的節點，然后再把兩個鏈表拼起來，

奇偶鏈表

代碼如下：

 /**
     * @return 奇偶鏈表
     * @Description:
     * @author 三分惡
     * @date 2021/7/25 22:18
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        //奇數位鏈表
        ListNode odd = new ListNode(-1);
        //偶數位鏈表
        ListNode even = new ListNode(-1);
        //奇、偶鏈表頭
        ListNode oddHead = odd;
        ListNode evenHead = even;
        //計算位置
        int index = 1;
        //遍歷
        ListNode cur = head;
        while (cur != null) {
            // 奇
            if (index % 2 == 1) {
                odd.next = cur;
                odd = odd.next;
            } else {
                //偶
                even.next = cur;
                even = even.next;
            }
            index++;
            cur = cur.next;
        }
        //防止成環
        even.next = null;
        //合并鏈表
        odd.next = evenHead.next;
        return oddHead.next;
    }

? 時間復雜度：O(n)，

劍指 Offer 25. 合并兩個排序的鏈表

? 題目：劍指 Offer 25. 合并兩個排序的鏈表(https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)

? 難度：簡單

📕 描述：

輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的節點仍然是遞增排序的，

示例1：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

本題與主站 21 題相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

💡 思路：

兩個升序鏈表，需要將其合并，那么我們需要創建一個新鏈表，遍歷兩個鏈表，把小的那個接在后面，

代碼如下：

   /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 劍指 Offer 25. 合并兩個排序的鏈表
     * @author 三分惡
     * @date 2021/7/25 22:36
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //新鏈表
        ListNode newNode = new ListNode(-1);
        //新鏈表偽頭
        ListNode newHead = newNode;
        while (l1 != null && l2 != null) {
            //插入小的節點
            if (l1.val <= l2.val) {
                newNode.next = l1;
                l1 = l1.next;
            } else {
                newNode.next = l2;
                l2 = l2.next;
            }
            newNode = newNode.next;
        }
        //最后一個節點不要漏了
        newNode.next = l1 != null ? l1 : l2;
        return newHead.next;
    }

? 時間復雜度：O(n)，

面試題 02.05. 鏈表求和

? 題目：面試題 02.05. 鏈表求和 (https://leetcode-cn.com/problems/sum-lists-lcci/)

? 難度：中等

📕 描述：

給定兩個用鏈表表示的整數，每個節點包含一個數位，

這些數位是反向存放的，也就是個位排在鏈表首部，

撰寫函式對這兩個整數求和，并用鏈表形式回傳結果，

示例：

輸入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
輸出：2 -> 1 -> 9，即912

**進階：**思考一下，假設這些數位是正向存放的，又該如何解決呢?

示例：

輸入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
輸出：9 -> 1 -> 2，即912

💡 思路：

這個就是我們上小學的時候很熟悉的四則運算，

兩個鏈表從頭，也就是個位開始計算，計算的結果，需要進位，我們用一個新鏈表來保存運算的結果，

如圖：

鏈表求和

代碼實作如下：

   /**
     * @return cn.fighter3.linked_list.ListNode
     * @Description: 面試題 02.05. 鏈表求和
     * @author 三分惡
     * @date 2021/7/26 2:40
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //新鏈表
        ListNode newNode = new ListNode(-1);
        //新鏈表頭
        ListNode newHead = newNode;
        //用來保存進制位
        int carry = 0;
        while (l1 != null || l2 != null) {
            //判斷當前位是否為空，為空則設定為0
            int l1Num = l1 == null ? 0 : l1.val;
            int l2Num = l2 == null ? 0 : l2.val;
            //求和
            int sum = l1Num + l2Num + carry;
            //更新進位
            carry = sum / 10;
            //求節點值
            int nodeNum = sum % 10;
            //添加節點
            newNode.next = new ListNode(nodeNum);
            //移動新鏈表指標
            newNode = newNode.next;
            //移動兩個鏈表指標
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        //最后根據進位，確定是否需要在尾部添加節點
        if (carry != 0) {
            newNode.next = new ListNode(carry);
        }
        return newHead.next;

    }

? 時間復雜度：O(n)，

總結

總結，我隨手寫了個順口溜，

鏈表總結

簡單的事情重復做，重復的事情認真做，認真的事情有創造性地做！

我是三分惡，一個能文能武的全堆疊開發，

點贊、關注不迷路，大家下期見！

博主是一個演算法萌新，刷題路線和思路主要參考以下大佬！建議關注！

參考：

[1].https://github.com/youngyangyang04/leetcode-master

[2].https://github.com/chefyuan/algorithm-base

[3].https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/lang-man-ai-qing-gu-shi-zou-yi-zou-dui-f-35vn/

[4].https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tu-jie-ken-ding-kan-de-ming-bai-by-xixili/

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290431.html

標籤：其他

上一篇：資料結構十大排序演算法+二分查找（左程云左神版全文2W字+ word很大，你忍一下~~）

下一篇：Linux中有關行程管理的命令

LeetCode通關：聽說鏈表是門檻，這就抬腳跨門而入

鏈表基礎

單鏈表

雙鏈表

回圈鏈表

鏈表的存盤方式

鏈表的定義

鏈表基本操作

鏈表操作

LeetCode203. 移除鏈表元素

LeetCode707. 設計鏈表

雙指標解決的題目

劍指 Offer 22. 鏈表中倒數第k個節點

LeetCode876. 鏈表的中間結點

LeetCode19. 洗掉鏈表的倒數第 N 個結點

劍指 Offer 52. 兩個鏈表的第一個公共節點

LeetCode206. 反轉鏈表

LeetCode92. 反轉鏈表 II

LeetCode234. 回文鏈表

LeetCode141. 環形鏈表

LeetCode142. 環形鏈表 II

雙鏈表問題

LeetCode86. 分隔鏈表

LeetCode328. 奇偶鏈表

劍指 Offer 25. 合并兩個排序的鏈表

面試題 02.05. 鏈表求和

總結