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;
}