每日三刷，劍指千題
計劃簡介：說明：
- 每日三題，以中等題為主，簡單題為輔進行搭配。保證品質題1道，數量題3道。
- 每日早通勤在LeetCode手機端選題，思考思路，沒答案的直接看題解。
- 每日中午進行編碼，時間控制在一小時之内。
- 下班前半小時進行整理總結。
- 基于以前的刷題基礎，本次計劃以中等題為主，大部分中等題都可以拆分為多個簡單題，是以數量保證3，品質保證一道中等題即可。
- 刷題順序按照先刷連結清單、二叉樹、棧、堆、隊列等基本資料結構，再刷遞歸、二分法、排序、雙指針等基礎算法，最後是動态規劃、貪心、回溯、搜尋等複雜算法。
- 刷題過程中整理相似題型，刷題模闆。
- 目前進度105/1000。
[61]旋轉連結清單
給你一個連結清單的頭節點
head
，旋轉連結清單，将連結清單每個節點向右移動
k
個位置。
示例 1：
輸入：head = [1,2,3,4,5], k = 2
輸出：[4,5,1,2,3] 解析
利用尋找連結清單的倒數的第K個結點時的雙指針法，找到倒數第k個節點和尾節點。把尾節點指向頭結點，此時連結清單成為一個環，再把連結清單從倒數第k個處斷開，即是旋轉後的連結清單。
但是，忽略了一個問題：
- 連結清單中節點的數目在範圍
[0, 500]
-
-100 <= Node.val <= 100
-
0 <= k <= 2 * 109
即 k 是可以大于連結清單的長度的，那這時候就需要對 k 取模，即假如連結清單長度是3 ，k = 4 和 k = 1 的結果是一樣的。那就先計算長度，再取模。
Code
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// 特例直接傳回
if (head == null) {
return head;
}
// 通過提示 先計算長度，再取模。簡化 k
int size = 0;
ListNode index = head;
while (index != null) {
index = index.next;
size++;
}
k = k % size;
// 這裡就是用過的雙指針了
ListNode first = head;
ListNode last = head;
for (int i = 0; i < k; i++) {
last = last.next;
}
while (last.next != null) {
first = first.next;
last = last.next;
}
// 先成環
last.next = head;
// 再從 k 處斷開
ListNode ans = first.next;
first.next = null;
return ans;
}
} [劍指 Offer 18]删除連結清單的節點
給定單向連結清單的頭指針和一個要删除的節點的值，定義一個函數删除該節點。
傳回删除後的連結清單的頭節點。
**注意：**此題對比原題有改動
示例 1:
輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你連結清單中值為 5 的第二個節點，那麼在調用了你的函數之後，該連結清單應變為 4 -> 1 -> 9. 解析
這是一道簡單題，思路不難，關鍵在于怎麼把代碼實作的夠優雅。
正常的思路都是判斷目前節點的 val 是否等于目标 val ，這樣就造成一個問題，我們好需要一個指針維護前一個結點來做删除操作。
如果我們增加一個虛拟頭結點，就可以判斷目前結點的下一個的 val 是否等于目标 val ，省去一個指針。
code
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head.val == val) return head.next;
ListNode dummy = new ListNode(0, head);
while (head.next != null) {
if (head.next.val == val) {
head.next = head.next.next;
break;
}
head = head.next;
}
return dummy.next;
}
} [劍指 Offer II 023]兩個連結清單的第一個重合節點
給定兩個單連結清單的頭節點
headA
和
headB
，請找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單沒有交點，傳回
null
。
圖示兩個連結清單在節點
c1
開始相交**：**
題目資料 保證 整個鍊式結構中不存在環。
注意，函數傳回結果後，連結清單必須 保持其原始結構 。
解析
這個就是主站的相交連結清單，做過一次，還是沒想起來。
思路不難，就是把兩個連結清單都走一遍，代碼實作上需要想一下。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while (A != B ) {
if (A == null) {
A = headB;
} else {
A = A.next;
}
if (B == null) {
B = headA;
} else {
B = B.next;
}
}
return A;
}
} B = headA;
} else {
B = B.next;
}
}
return A;
}
}