Intersection of Two Linked Lists
题目
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.
思路
分别计算两个链表的长度l1和l2,若l1>l2,p=headA,q=headB,p先行l1-l2步，然后p和q同时移动。同理，l1<l2,p=headA,q=headB,q先行l2-l1步，然后p和q同时移动。返回p和q相等的结点。
解题
c++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA=0,lenB=0,count;
ListNode *cur,*p,*q;
cur=headA;
while(cur){
lenA++;
cur=cur->next;
}
cur=headB;
while(cur){
lenB++;
cur=cur->next;
}
p=headA;
q=headB;
if(lenA>lenB){
count=lenA-lenB;
while(count--)
p=p->next;
}
else{
count=lenB-lenA;
while(count--)
q=q->next;
}
while(p!=q){
p=p->next;
q=q->next;
}
return p;
}
};
|
python版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution:
def getIntersectionNode(self, headA, headB):
pA = headA
pB = headB
lenA=0
lenB=0
while(pA):
lenA+=1
pA=pA.next
while(pB):
lenB+=1
pB=pB.next
if lenA<=lenB:
n=lenB-lenA
pA = headA
pB = headB
while(n):
pB=pB.next
n=n-1
else:
n=lenA-lenB
pA = headA
pB = headB
while(n):
pA=pA.next
n=n-1
while pA!=pB:
pA=pA.next
pB=pB.next
return pA
|
