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=)