难度：Easy
解题思路：一个链表长度x+y，另一个z+y，则两个节点分别从两个链表的head出发，走到头后，走向另一个链表的头。当两者共同走x+y+z时，遇到相同节点。
代码如下：
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
|
/**
* 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) {
if(headA == NULL || headB == NULL)
return NULL;
ListNode *curA = headA;
ListNode *curB = headB;
while(true)
{
if(curA == curB)
return curA;
else
{
if(curA->next != NULL && curB->next != NULL)
{
curA = curA->next;
curB = curB->next;
}
else if(curA->next == NULL && curB->next != NULL)
{
curB = curB->next;
curA = headB;
}
else if(curB->next == NULL && curA->next != NULL)
{
curB = headA;
curA = curA->next;
}
else
return NULL;
}
}
}
};
|
运行结果：52ms，超过28.14%
近期评论