题目

  • 输入两个链表,找出它们的第一个公共节点。

示例

  • 示例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 次。如果第一次走的如果是长的,那第二次就走的是短的;如果第一次走的如果是短的,那第二次就走的是长的,如此两个指针相汇时走的次数是相等的

本文题目liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof