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.
如果两个链表有重复的部分，那么返回重复的起始位置，否则，返回null。
两种方法：
1、（参考discuss中，并非最佳答案）
可以利用hashMap，先把第一个链表的所有节点放入map中，然后再遍历第二个链表，看map中是否有相同的节点。如果没有，返回null。
时间复杂度O(m+n),空间复杂度O(m) or O(n)
2、先遍历一次链表，找出连个链表的最后一个节点（如果不一样，那么返回null）以及长度差（最佳）
然后较长的链表先走长度差个节点，
之后两个链表一起走，遇到相同的就返回。
时间复杂度O(m+n),空间复杂度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) {
int len1 = 1,len2 = 1;
if( headA == null || headB == null)
return null;
ListNode node1 = headA;
ListNode node2 = headB; while( node1.next != null ){
node1 = node1.next;
len1++;
}
while( node2.next != null ){
node2 = node2.next;
len2++;
}
if( len1 == 0 || len2 == 0 || node1 != node2 )
return null;
node1 = headA;
node2 = headB;
if( len1 > len2 ){
while( len1 > len2 ){
len1--;
node1 = node1.next;
}
}else if( len1 < len2 ){
while( len1<len2){
len2--;
node2 = node2.next;
}
} while( len1 >0 ){
if( node1 == node2 )
return node1;
node1 = node1.next;
node2 = node2.next;
len1--;
}
return null;
}
}
3、（参考discuss）
不用第一次遍历找出长度差，一直循环遍历找出相同的节点（如果不存在会出现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) {
//boundary check
if(headA == null || headB == null) return null; ListNode a = headA;
ListNode b = headB; //if a & b have different len, then we will stop the loop after second iteration
while( a != b){
//for the end of first iteration, we just reset the pointer to the head of another linkedlist
a = a == null? headB : a.next;
b = b == null? headA : b.next;
} return a;
}
}