160. 相交連結清單
給你兩個單連結清單的頭節點 headA 和 headB ，請你找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單不存在相交節點，傳回 null 。
圖示兩個連結清單在節點 c1 開始相交：
【03/17】力扣押題推薦(相交連結清單、環形連結清單2、合并K個升序連結清單) 題目資料 保證 整個鍊式結構中不存在環。
注意，函數傳回結果後，連結清單必須 保持其原始結構 。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節點的值為 8 （注意，如果兩個連結清單相交則不能為 0）。
從各自的表頭開始算起，連結清單 A 為 [4,1,8,4,5]，連結清單 B 為 [5,6,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
示例 2：
輸入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節點的值為 2 （注意，如果兩個連結清單相交則不能為 0）。
從各自的表頭開始算起，連結清單 A 為 [1,9,1,2,4]，連結清單 B 為 [3,2,4]。
在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。
題解：
// 雙指針周遊
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
// 分别周遊兩個連結清單
// 如果周遊完目前連結清單，則指針指向另一個連結清單的頭
// 知道兩個指針相遇
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
// hash表存儲
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
// 首先周遊連結清單 headA，并将連結清單 headA 中的每個節點加入哈希集合中。
// 然後周遊連結清單 headB，對于周遊到的每個節點，判斷該節點是否在哈希集合中：
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
// 如果目前節點不在哈希集合中，則繼續周遊下一個節點；
// 如果目前節點在哈希集合中，則後面的節點都在哈希集合中，即從目前節點開始的所有節點都在兩個連結清單的相交部分
// 是以在連結清單 headB 中周遊到的第一個在哈希集合中的節點就是兩個連結清單相交的節點，傳回該節點。
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
} 142. 環形連結清單 II
給定一個連結清單的頭節點 head ，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。
如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，評測系統内部使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。如果 pos 是 -1，則在該連結清單中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。
不允許修改連結清單。
示例 1：
【03/17】力扣押題推薦(相交連結清單、環形連結清單2、合并K個升序連結清單) 輸入：head = [3,2,0,-4], pos = 1
輸出：傳回索引為 1 的連結清單節點
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：傳回索引為 0 的連結清單節點
解釋：連結清單中有一個環，其尾部連接配接到第一個節點
題解：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) { // 快慢指針
// 如果連結清單是null，或者隻有一個就沒有環，直接傳回null
if (head == null || head.next == null){
return null;
}
ListNode i = head; // 設定慢節點
ListNode j = head; // 設定快節點
// 循環周遊找重合點
while (true) {
// 如果快指針周遊結束，證明沒有環
if (j.next == null || j.next.next == null) {
return null;
}
i = i.next; // 慢指針一次移動一位
j = j.next.next; // 快指針一次移動兩位
if (i == j) { // 如果快慢指針重合，證明有環
break;
}
}
// 将慢指針重新指向頭結點
i = head;
// j指針 位置不變 ，将i指針重新 指向連結清單頭部節點 ；i和j同時每輪向前走n步； 此時f=0,s=nb；
// 當i指針走到f=a步時，j指針走到步s=a+nb，此時 兩指針重合，并同時指向連結清單環入口 。
// 重新循環，傳回索引為 1 (pos = 1)的連結清單節點(連結清單環入口)
while (i != j) {
i = i.next;
j = j.next;
}
return i;
}
public ListNode detectCycle(ListNode head) { // hash表
// 如果連結清單是null，或者隻有一個就沒有環，直接傳回null
if (head == null || head.next == null) {
return null;
}
Set set = new HashSet<ListNode>();
ListNode i = head;
// 周遊連結清單，周遊的值如果存在hash表中，則證明有環
while (i != null) {
if (set.contains(i)) {
return i;
} else {
set.add(i);
}
i = i.next;
}
return null;
}
} 23. 合并K個升序連結清單
給你一個連結清單數組，每個連結清單都已經按升序排列。
請你将所有連結清單合并到一個升序連結清單中，傳回合并後的連結清單。
示例 1：
輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：連結清單數組如下：
[
1->4->5,
1->3->4,
2->6
]
将它們合并到一個有序連結清單中得到。
1->1->2->3->4->4->5->6
示例 2：
輸入：lists = []
輸出：[]
示例 3：
輸入：lists = [[]]
輸出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的總和不超過 10^4
// K指針：K 個指針分别指向 K 條連結清單
// 每次 O(K) 比較 K個指針求 min, 時間複雜度：O(NK)
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (true) {
ListNode minNode = null;
int minPointer = -1;
for (int i = 0; i < k; i++) {
if (lists[i] == null) {
continue;
}
if (minNode == null || lists[i].val < minNode.val) {
minNode = lists[i];
minPointer = i;
}
}
if (minPointer == -1) {
break;
}
tail.next = minNode;
tail = tail.next;
lists[minPointer] = lists[minPointer].next;
}
return dummyHead.next;
}
// 我們可以想到一種最樸素的方法
// 用一個變量 ans 來維護以及合并的連結清單
// 第 i 次循環把第 i 個連結清單和 ans 合并，答案儲存到 ans 中。
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
for (int i = 0; i < lists.length; ++i) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}