题目
- 输入两个链表，找出它们的第一个公共节点。
示例
- 示例1
输入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
输出：8
- 示例2
输入：listA = [0,9,1,2,4], listB = [3,2,4]
输出：2
代码
- 双指针 O(m+n)
// Java
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode PA = headA;
ListNode PB = headB;
while (PA != PB) {
PA = PA == null ? headB : PA.next;
PB = PB == null ? headA : PB.next;
}
return PA;
}
}
// C++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *node1 = headA;
ListNode *node2 = headB;
while (node1 != node2) {
node1 = node1 != NULL ? node1->next : headB;
node2 = node2 != NULL ? node2->next : headA;
}
return node1;
}
};
代码分析：题解from 这道题解非常巧妙
1、两个链表长度很大可能不相等，那怎么找出他们公共的部分呢？
2、解题思路：
我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
3、为什么这样做就可行？因为 node1 和 node2 最多只会走 m+n 次。如果第一次走的如果是长的，那第二次就走的是短的；如果第一次走的如果是短的，那第二次就走的是长的，如此两个指针相汇时走的次数是相等的。
