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.
第一种方法:
暴力破解：
依次循环每一个节点，比较是否相等。时间复杂度O(Length(A)*Length(B)),空间复杂度O（1）
public static LinkNode getIntersectionNode(LinkNode headA, LinkNode headB) {
if(headA == null || headB == null){
return null;
}
LinkNode tmp = headA;
while(headB != null){
headA = tmp;
while(headA != null){
if(headB == headA){
return headB;
}else{
headA = headA.next;
}
}
headB = headB.next;
}
return null;
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
最后的执行结果是time Limited，好吧。。。。。。。。。。。。。
第二种
哈希表法，
将其中的一个链表散列到哈希表里，然后查找另一个链表的元素是不是在哈希表里时间复杂度O(lengthA+lengthB)，空间复杂度O(lengthA)或O(lengthB)。
第三种：
1、先各自遍历每一个链表，计算链表长度，都到达末尾时，如果末尾节点相同，说明有交集，否则返回null
2、如果有交集的话，先让长链表走|Length（A）-Length（B）|步，再同时走，比较可以找到
时间复杂度O(lengthA+lengthB)，空间复杂度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;
}
int c1=1;
int c2=1;
ListNode h1 = headA;
ListNode h2 = headB;
while(h1.next != null){
c1++;
h1 = h1.next;
}
while(h2。next != null){
c2++;
h2 = h2.next;
}
if(h1 != h2){
return null;
}
if(c1 > c2){
int c = c1 - c2;
while(c > 0){
headA = headA.next;
c--;
}
}
if(c1 < c2){
int c = c2 - c1;
while(c > 0){
headB = headB.next;
c--;
}
}
while(headA != null && headA != headB){
headA = headA.next;
headB = headB.next;
}
return headA;
}
}
Runtime: 520 ms
第四种：
先分析下，
第一种方法是暴力破解，思路很简单，效率去很低（这是我自己可以想到的，哎，脑子还是太笨。。。）
第二种方法是哈希表法，利用哈希表的查找时间复杂度是O(1)的性质，最终的缺点在于空间复杂度上，需要create一个HashSet，（压根没有想到哈希表，不善于使用hash，以后得记住点这个，作为解题得思路）
第三种方法比较好，计算出两条链表的长度差，先让长的走，然后一起走，如果两条链有交集，那么，|length（A）-Length（B）|就一定不是，因此可以去掉这些无用的遍历，即让长的先走|length（A）-Length（B）|，
到这一步之后怎么继续改进？
能不能不计算链表长度就得到这个差值？答案是可以。
作者提供的解题方法：
-
Brute-force solution (O(mn) running time, O(1) memory):
For each node a i in list A, traverse the entire list B and check if any node in list B coincides with a i .
-
Hashset solution (O(n+m) running time, O(n) or O(m) memory):
Traverse list A and store the address / reference to each node in a hash set. Then check every node b i in list B: if b i appears in the hash set, then b i is the intersection node.
- Two pointer solution (O(n+m) running time, O(1) memory):
- Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
- When pA reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when pB reaches the end of a list, redirect it the head of A.
- If at any point pA meets pB, then pA/pB is the intersection node.
- To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
- If two lists have intersection, then their last nodes must be the same one. So when pA/pB reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.
同时遍历两个链表（在这里就可以先进行比较了，找到就返回），当其中的一个链表到达尾部时，另一个一定是在差值的那个地方，那么就是找到这个差值了，然后再同时遍历。依次maintain两个pointer Pa和Pb，当到达尾部时（假设Pa先到达尾部，说明headB长），pa=headB，pb=headA
这是作者提供的解法。
/**
* 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 pa = headA;
ListNode pb = headB;
while(pa != null && pb != null){
if(pa == pb){
return pa;
}
pa = pa.next;
pb = pb.next;
}
//
if(pa == null && pb != null){//链表b比较长
pa = headB;
while(pb != null){//
pa = pa.next;
pb = pb.next;
}
pb = headA;
while(pa !=null && pb != null){
if(pa == pb){
return pa;
}
pa = pa.next;
pb = pb.next;
}
}else if(pb == null && pa != null){
pb = headA;
while(pa != null){
pb = pb.next;
pa = pa.next;
}
pa = headB;
while(pa != null && pb != null){
if(pa == pb){
return pa;
}
pa = pa.next;
pb = pb.next;
}
}
return null;
}
}
Runtime: 504 ms
还是自己的脑子不够活泛，不能从多角度思考问题，之前自己想的时候一直在想怎么能够快速定位到这个交集点，总是没有头绪，感觉除了一个个遍历比较再没有其他的方法。再看别人写的，发现改进还是有的。不考虑空间复杂度的话，将一个数组映射到hash表里，然后遍历第二个数组，可以用O（1）的时间找到是否有相等的量。考虑空间复杂度的话，那么就要考虑怎么减少遍历的次数，就是去掉不必要的比较。比如说，如果两个链表存在交集点，如果两个链表长度相等，那么就没有冗余的比较了，如果链表长度不相等，那么较长链表（假设B长）的前Length（B）-Length（A）个元素与较短链表的比较就是冗余的，因为前Length（B）-Length（A）个元素不可能是交集点。所以考虑如何跳过这些元素（比如找到计算链表长度，然后再跳过差值，显然计算链表长度的时间要小于遍历这些元素并且比较的时间，一开始思维总是感觉遍历比较简单就觉得花的时间少）。作者提出的这个计算差值的方法还是不错的（learning...）
![力扣每日一题：65. 有效数字题目：65. 有效数字解题思路[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)