两个链表的公共节点

两个链表的公共节点

时间限制:1秒 空间限制:32768K

题目描述

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

题目分析

我们首先定义两个辅助栈,然后依次将两个链表的节点压入栈中,然后从栈顶再依次往下比较两个栈的元素,直到遇到第一个不相等的节点时,前一个节点就是两个链表的公共节点。

代码实现

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        vector<ListNode*>list1;
        vector<ListNode*>list2;
        while(pHead1)
        {
            list1.push_back(pHead1);
            pHead1 = pHead1->next;
        }

        while(pHead2)
        {
            list2.push_back(pHead2);
            pHead2 = pHead2->next;
        }
        int i = list1.size() - 1;
        int j = list2.size() - 1;
        while(i >= 0 && j >= 0)
        {
            if(list1[i] != list2[j])
            {
                break;
            }
            i--;
            j--;
        }
        if(i == list1.size() - 1)
            return NULL;
        return list1[i+1];
    }
};
    原文作者:--FGC--
    原文地址: https://blog.csdn.net/flyingsbird/article/details/81083857
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞