Description
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null
.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
Credits:Special thanks to @stellari for adding this problem and creating all test cases.
Solution
Two iterations with counting length
先遍歷一遍花吟，計(jì)算出兩個(gè)list的長度。然后讓長的鏈表的頭指針多走幾步，之后雙指針一起走直到相遇（可能為null）压昼。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int l1 = getLength(headA);
int l2 = getLength(headB);
if (l1 < l2) {
return getIntersectionNode(headB, headA);
}
// make sure l1 >= l1
for (int i = l2; i < l1; ++i) {
headA = headA.next;
}
while (headA != headB) { // iterate until two list meet
headA = headA.next;
headB = headB.next;
}
return headA;
}
private int getLength(ListNode head) {
int len = 0;
while (head != null) {
++len;
head = head.next;
}
return len;
}
}
Two iterations without counting length
其實(shí)沒有必要計(jì)算list length石蔗，只需要排除掉長度差距即可蠢涝，可以在第一遍遍歷時(shí)如果走到null則切換到另一個(gè)list head派阱，這樣兩個(gè)指針就可以到同一個(gè)起跑線了切诀。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while (p != q) {
p = p != null ? p.next : headB;
q = q != null ? q.next : headA;
}
return p;
}
}
Follow-up: How to detect if two linked lists have intersection?
其實(shí)比原題目簡單揩环，因?yàn)橹恍枰祷豣oolean即可，基本有下面幾種做法：
- 將ListA的所有節(jié)點(diǎn)存入HashSet中幅虑，然后遍歷ListB丰滑，看是否有重合。
- 兩個(gè)鏈表如果相交倒庵，tail node一定相同褒墨。那么可以找到tailA和tailB炫刷，比較是否相等即可。
但是這里有一個(gè)坑貌亭。如果input list有環(huán)怎么辦柬唯？這樣就找不到tail了认臊。這種情況下圃庭，需要結(jié)合HashSet + findTail兩種做法，對于listB來說失晴，find tail的同時(shí)查詢HashSet中是否已經(jīng)有該節(jié)點(diǎn)剧腻，如果有那么當(dāng)前節(jié)點(diǎn)即為偽tail；否則將節(jié)點(diǎn)加入到HashSet中涂屁。
遍歷listB時(shí)也要維護(hù)listB的HashSet书在，如果listB已經(jīng)遍歷一圈還沒有遇到和listA的intersection，即為不相交拆又。
