Leetcode-160. 相交链表

160. 相交链表

解法:快慢指针

我们需要做的事情是,让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此,我们必须消除两个链表的长度差

指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
如果 pA 到了末尾,则 pA = headB 继续遍历
如果 pB 到了末尾,则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时,长度差就消除了
如此,只需要将最短链表遍历两次即可找到位置

如果两链表不相交,则遍历两次后,都指向空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 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) {
auto a=headA;
auto b=headB;
while(a!=b)
{
a= a==NULL?headB:a->next;
b= b==NULL?headA:b->next;
}
return a;
}
};