-
題目：
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
- 保持原來的結(jié)構(gòu)不變
- 確保沒有環(huán)
- 時間復(fù)雜度為O（n）蒿辙，空間復(fù)雜度為O（1）
其中第一條和最后一條注意事項是最重要的熊镣，個人覺得這道題雖然在LeetCode上面是easy難度的吓肋，但是涉及到的內(nèi)容還是挺不少的签孔，因為有最后一條注意事項的限制，所以需要結(jié)合時間復(fù)雜度和空間復(fù)雜度來進行算法定制华临，對于本題芯杀，本文一共會列出三種算法來求解，并同時分析算法復(fù)雜度和時間復(fù)雜度雅潭。
-
三種算法的分析：
-
直接法：
遍歷鏈表A揭厚，對于每一個遍歷的節(jié)點都遍歷一次鏈表B，判斷是否有節(jié)點相同扶供，這種算法是最簡單的筛圆，但是效率不高
- 時間復(fù)雜度：O（n * n）
- 空間復(fù)雜度：O（1）
顯然是不能滿足要求的，時間復(fù)雜度不是一個級別的
-
哈希表求解法
先遍歷鏈表A椿浓，將鏈表A的每個節(jié)點放入哈希表中顽染，然后遍歷鏈表B漾岳，對于每個節(jié)點都利用哈希表進行判斷，看是否存在相同的節(jié)點
- 時間復(fù)雜度：O（n）
- 空間復(fù)雜度：O（n）
這里時間復(fù)雜度是滿足了O（n）粉寞，但是空間復(fù)雜度卻由于創(chuàng)建了哈希表而變成了O（n）
-
雙指針求解法
兩個鏈表的長度是不一樣的，但是重疊部分是一樣的左腔，也就是說后半部分是一樣的唧垦，那么就可以將長的鏈表的前半部分給裁剪了，然后將裁剪后的鏈表的起始節(jié)點作為第一個節(jié)液样，然后同時遍歷兩個鏈表進行判斷是否相同振亮，所以時間復(fù)雜度僅僅為O（n）
- 時間復(fù)雜度：O（n）
- 空間復(fù)雜度：O（1）
這就是最符合題目的求解方法，從這道題也能看出來算法的重要性鞭莽，他能夠提高空間和時間的效率
-
直接法：
代碼：
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *nodeA = headA;
ListNode *nodeB = headB;
int lengthA = 0;
int lengthB = 0;
while(headA) {
lengthA++;
headA = headA->next;
}
while(headB) {
lengthB++;
headB = headB->next;
}
if (lengthA >= lengthB) {
int difference = lengthA - lengthB;
for (int i = 0; i < difference; i++) {
nodeA = nodeA->next;
}
} else {
int difference = lengthB - lengthA;
for (int i = 0; i < difference; i++) {
nodeB = nodeB->next;
}
}
while(nodeA!=nodeB) {
nodeA = nodeA->next;
nodeB = nodeB->next;
}
return nodeA;
}
