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.
一刷
題解：
如果A,B長度相同，那么直接同步next就能找到埃脏。
如果B比A長n個點(diǎn)，那么當(dāng)a到達(dá)尾部時酿矢，b滯后n個點(diǎn)蠢终。然后a從B開始，b從A開始飘痛。那么a和b剩余的長度相同晚胡。
time complexity O(n), space complexity O(1)
/**
* 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) {
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while(a!=b){
a = a==null? headB : a.next;
b = b==null? headA : b.next;
}
return a;
}
}
二刷
思路同上
/**
* 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) {
ListNode a = headA, b = headB;
while(a!=b){
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
}
