Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘
c1 → c2 → c3
↗
B:b1 → b2 → b3
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.
題意：看兩個(gè)鏈表宪摧，是否有交點(diǎn)鬓梅，之后都合并在了一起址愿。
思路：兩個(gè)鏈表可能長度不一樣長从诲，我們需要把長的頭指針先往后走，直至兩個(gè)鏈表等長的時(shí)候再菊，然后這個(gè)時(shí)候族奢，兩個(gè)頭指針懈玻，同時(shí)往后走女轿，看看是否能走到同一個(gè)節(jié)點(diǎn)箭启，如果走到了，直接返回這個(gè)結(jié)點(diǎn)就可以了蛉迹。
java代碼：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
int lenA = getLength(headA), lenB = getLength(headB);
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
} else {
for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
}
while (headA != null && headB != null && headA != headB) {
headA = headA.next;
headB = headB.next;
}
return (headA != null && headB != null) ? headA : null;
}
public int getLength(ListNode head) {
int cnt = 0;
while (head != null) {
++cnt;
head = head.next;
}
return cnt;
}
}
