剑指offer-刷题笔记-简单题-JZ52 两个链表的第一个公共结点

剑指offer-刷题笔记-简单题-JZ52 两个链表的第一个公共结点,第1张

剑指offer-刷题笔记-简单题-JZ52 两个链表的第一个公共结点 版本1-自己写的,不正确,开始认为不断的删除链表1的节点,直到链表2的长度减少,则删除的节点为公共节点。
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    int GetListLength(ListNode* pHead)
    {
        int index = 0;
        while(pHead)
        {
            pHead = pHead->next;
            index++;
        }
        return index;
    }
    
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        //pHead1段节点
        vector< ListNode* > listNodeVec;
        int listLength2  = GetListLength(pHead2);

        if(GetListLength(pHead1) <= 1 || GetListLength(pHead2) <= 1)
        {
            return nullptr;
        }
        //ListNode* pHead = pHead1;
        int count = 0;
        while(pHead1)
        {  
            ListNode* pHead = pHead1;
            pHead1= pHead1->next;
            listNodeVec.push_back(pHead1);
            free(pHead);;  
            if(GetListLength(pHead2) < listLength2)
            {
                //cout<
                break;
            }
            count ++;
              
        }
        cout<<listNodeVec.size()<<endl;
        if(count == 0)
        {
            //cout<<"ddd"<
            return listNodeVec[0];
        }else{
            return listNodeVec[0];
        }
        
    }
};
版本2-双指针,因为两个链表非公共部分长度不一致,所以将两个链表链接为一个链表,这样原来的链表就具有同样的长度,可同时进行遍历,即原来 list1,a+b,list2,c+b,之后list1,c+b+a+b,list2,a+b+c+b,
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *ta = pHead1, *tb = pHead2;
        while (ta != tb) {
            ta = ta ? ta->next : pHead2;
            tb = tb ? tb->next : pHead1;
        }
        return ta;
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/732525.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-27
下一篇 2022-04-27

发表评论

登录后才能评论

评论列表(0条)

保存