請寫一個程序织盼，找到兩個單鏈表最開始的交叉節(jié)點。
注意事項
如果兩個鏈表沒有交叉酱塔，返回
null沥邻。
在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)羊娃。
可假定整個鏈表結(jié)構(gòu)中沒有循環(huán)唐全。
樣例
下列兩個鏈表：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在節(jié)點 c1 開始交叉。
挑戰(zhàn)
需滿足 O(n) 時間復(fù)雜度，且僅用 O(1) 內(nèi)存
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// 找到鏈表 A 的尾結(jié)點
ListNode node = headA;
while (node.next != null) {
node = node.next;
}
// 鏈表 A 的尾結(jié)點和鏈表 B 的頭結(jié)點連在一起
node.next = headB;
ListNode result = listCycleII(headA);
return result;
}
// 尋找?guī)Лh(huán)鏈表的環(huán)的入口
private ListNode listCycleII(ListNode head) {
ListNode slow = head, fast = head.next;
// 先判斷是否存在環(huán)
while (slow != fast) {
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
slow = head;
// 注意此處 fast 前進一個結(jié)點
fast = fast.next;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
