题目描述

求两个链表的公共节点

样例

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[1, 2, 3, 4, 5, 6, 7]

10(?)

(标记法) $O(n)$

new一个新节点 遍历A 所有A节点都指向标记节点 遍历B 发现某一个点指向标记节点 说明是公共节点

C++ 代码

  ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* flag=new ListNode(-1);//new一个标记节点
        ListNode* cur=headA;//cur是当前指针
        while(cur!=NULL)//遍历链表A
        {
            ListNode* temp=cur->next;//保存一下（当前节点的下一个节点）

            cur->next=flag;//另当前cur节点next指向标记节点
            cur=temp;//下一个节点
        }
        cur=headB;
        while(cur!=NULL)//遍历B链表 如果发现某一个点的next指向标记节点 说明是公共节点
        {
            if(cur->next==flag)return cur;
            else cur=cur->next;
        }
        return NULL;//没搜索到就返回空节点
    }

(差值法) $O(n+m)$

如果二者一样长 可以简单的用双指针同时移动遍历2个链表
但是不一样长的话需要算出偏移量M
长的先走M个点（因为公共节点开始 长度一样 长度不一样的部分只能在公共节点之前 先走的部分不会涉及到公共节点）

C++ 代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur1=headA;
        ListNode* cur2=headB;
        int cnt1=0;
        int cnt2=0;
        while(cur1!=NULL)//遍历A链表
        {
            cnt1++;
            cur1=cur1->next;
        }
        while(cur2!=NULL)//遍历B链表
        {
            cnt2++;
            cur2=cur2->next;
        }
        cur1=headA;
        cur2=headB;
        if(cnt1>cnt2)
        {
            for(int i=0;i<cnt1-cnt2;i++)cur1=cur1->next;//长的先走差值M个单位
            while(cur1!=NULL)//长度一样就可以双指针遍历了
            {
                if(cur1==cur2)return cur1;
                else 
                {
                    cur1=cur1->next;
                    cur2=cur2->next;
                }
            }
        }
        else{
            for(int i=0;i<cnt2-cnt1;i++)cur2=cur2->next;
            while(cur2!=NULL)
            {
                if(cur1==cur2)return cur2;
                else 
                {
                    cur1=cur1->next;
                    cur2=cur2->next;
                }
            }
        }
        return NULL;
    }