剑指 Offer 52. 两个链表的第一个公共节点

题目描述

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

解答

遍历，虽然觉得样例可能有点问题。。。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *h1=NULL, *h2=NULL;
        while (headA!=NULL){
            if (h1==NULL)
            {
                h1=new ListNode;
                h1->val=headA->val;
                h1->next=NULL;
            }
            else
            {
                ListNode *p=new ListNode;
                p->val=headA->val;
                p->next=h1;
                h1=p;
            }
            headA=headA->next;
        }

        while (headB!=NULL){
            if (h2==NULL)
            {
                h2=new ListNode;
                h2->val=headB->val;
                h2->next=NULL;
            }
            else
            {
                ListNode *p=new ListNode;
                p->val=headB->val;
                p->next=h2;
                h2=p;
            }
            headB=headB->next;
        }

        ListNode *h3=NULL;
       
        while(h1!=NULL && h2!=NULL && h1->val==h2->val)
        {
            if (h3==NULL)
            {
                h3=new ListNode;
                h3->val=h1->val;
                h3->next=NULL;
            }
            else
            {
                ListNode *p=new ListNode;
                p->val=h1->val;
                p->next=h3;
                h3=p;                
            }
            h1=h1->next;
            h2=h2->next;
        }
        return h3;
    }
};

BUG

8 [4,1,8,4,5] [5,0,1,8,4,5] 2 3

输出

Intersected at '1'

预期结果

Intersected at '8'