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.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//想法一:length1 - length2 = dis;兩個指針,長的連結清單先走dis步,然後一起走,指導遇見相同的節點。
//特殊情況:空連結清單,連結清單在頭結點相交,連結清單在尾節點相交
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB) return NULL;
if(headA==headB) return headA;
// 周遊兩個連結清單,得到兩個連結清單的長度
ListNode *pA = headA;
ListNode *pB = headB;
int lengthA=0,lengthB=0;
while(pA){//注意條件判斷
lengthA++;
pA = pA->next;
}
while(pB){
lengthB++;
pB = pB->next;
}
ListNode *longlist = (lengthA>=lengthB)?headA:headB;
ListNode *shortlist = (lengthA>=lengthB)?headB:headA;
int dis = abs(lengthA-lengthB);
for(int i=0;i<dis;i++){
longlist = longlist->next;
}
while(longlist){
if(longlist==shortlist) return longlist;
longlist = longlist->next;
shortlist = shortlist->next;
}
return NULL;
}
};