LeetCode通關：聽說鏈表是門檻，這就抬腳跨門而入
- 2021 年 7 月 26 日
- 筆記
- 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. 移除鏈表元素 (//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. 設計鏈表 (//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. 設計鏈表
* //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個節點 (//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是倒數第二個。
程式碼實現：
/**
* 劍指 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. 鏈表的中間結點 (//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 個結點 (//leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
❓ 難度：中等
📕 描述：給你一個鏈表，刪除鏈表的倒數第 n 個結點，並且返回鏈表的頭結點。
進階：你能嘗試使用一趟掃描實現嗎？
💡 思路：
這道題上手是不是就覺得很熟？
這是 203.移除鏈表元素 和 劍指 Offer 22. 鏈表中倒數第k個節點 的結合。
那麼解法，我們同樣可以結合這兩道題。
- 快慢指針找到倒數第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. 鏈表的中間結點 (//leetcode-cn.com/problems/middle-of-the-linked-list/)
❓ 難度：簡單
📕 描述：給定一個頭結點為 head 的非空單鏈表，返回鏈表的中間結點。
如果有兩個中間結點，則返回第二個中間結點。
💡 思路：
他們都說這道題浪漫，我卻不想聽什麼狗屁的浪漫愛情故事，我只想搞錢。
這道題可以用雙指針解決，定義兩個指針，當某一指針遍歷完鏈表之後，然後掉頭去另一個鏈表的頭部，繼續遍歷。因為速度相同所以他們第二次遍歷的時候肯定會相遇。
如圖（來自參考[3]）：
![圖片來自參考[3]](http://img-blog.csdnimg.cn/img_convert/4e3db662bffca060aa82e61aae30baf3.png)
程式碼實現：
/**
* 劍指 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. 反轉鏈表 (//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 (//leetcode-cn.com/problems/reverse-linked-list-ii/)
❓ 難度：中等
📕 描述：給你單鏈表的頭指針 head 和兩個整數 left 和 right ，其中 left <= right 。請你反轉從位置 left 到位置 right 的鏈表節點，返回 反轉後的鏈表 。
💡 思路：
反轉鏈表經常容易忘，我們再做一道進階的題目來鞏固一下。
這道題什麼思路呢？
我們可以把反轉的這一部分拆出來，作為新的鏈表，反轉新鏈表，然後再和前後的節點重新連接。
程式碼實現：
/**
* @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. 迴文鏈表(//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. 環形鏈表 (//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 (//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]](http://img-blog.csdnimg.cn/img_convert/48b00fac285ef83c78654f04dbccd8c6.png)
程式碼實現：
/**
* @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. 分隔鏈表 (//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. 奇偶鏈表 (//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. 合併兩個排序的鏈表(//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 題相同：//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. 鏈表求和 (//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].//github.com/youngyangyang04/leetcode-master
[2].//github.com/chefyuan/algorithm-base
