分門别類刷算法，堅持，進步！
刷題路線參考：
https://github.com/youngyangyang04/leetcode-master https://github.com/chefyuan/algorithm-base
連結清單基礎
在開始刷題之前，我們最好先了解一下連結清單的一些基礎知識，那麼現在，我們開始吧。
連結清單是一種鍊式存儲的線性表，不要求邏輯上相鄰的資料元素在實體位置上也相鄰。
單連結清單
一個單向連結清單包含兩個值: 目前節點的值和一個指向下一個節點的引用。也可以稱之為資料域和指針域。
入口節點稱為頭結點，最後一個節點指向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)。
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是倒數第二個。
代碼實作：
/**
* 劍指 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;
} 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;
} LeetCode19. 删除連結清單的倒數第 N 個結點
☕ 題目：19. 删除連結清單的倒數第 N 個結點 (https://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;
} 劍指 Offer 52. 兩個連結清單的第一個公共節點
head
他們都說這道題浪漫，我卻不想聽什麼狗屁的浪漫愛情故事，我隻想搞錢。
這道題可以用雙指針解決，定義兩個指針，當某一指針周遊完連結清單之後，然後掉頭去另一個連結清單的頭部，繼續周遊。因為速度相同是以他們第二次周遊的時候肯定會相遇。
如圖（來自參考[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
說真的，作為一個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;
} LeetCode92. 反轉連結清單 II
☕ 題目：92. 反轉連結清單 II (https://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;
} 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;
} 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;
} 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(1)，這就涉及到非常巧妙的一個雙指針做法。
下圖是一種比較典型的情況下，做的推導[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;
} 雙連結清單問題
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;
} 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;
} 劍指 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;
} 面試題 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;
} 總結
總結，我随手寫了個順口溜。
簡單的事情重複做，重複的事情認真做，認真的事情有創造性地做！
我是
，一個能文能武的全棧開發。三分惡
點贊
不迷路，大家下期見！關注