剑指offer:两个链表的第一个公共节点

港控/mmm° 2022-04-10 09:13 194阅读 0赞

## 题目描述 ##

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

AC C++ Solution:

思路: 因为第一个公共节点后面所有的节点都相同,首先计算两链表的长度差,抹平长度差距,然后再同时遍历,找到第一个公共节点

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            if(pHead1 == NULL || pHead2 == NULL)
                return NULL;
            
            int dif = 0;            //两链表长度差
            int m = 0, n = 0;
            ListNode* p1 = pHead1;
            ListNode* p2 = pHead2;
            
            while(p1)  {
                m++;
                p1 = p1->next;
            }
            while(p2) {
                n++;
                p2 = p2->next;
            }
            
            if(m >= n) {
                dif = m-n;
                while(dif--)
                    pHead1 = pHead1->next;
            }
            
            else {
                dif = n - m;
                while(dif--)
                    pHead2 = pHead2->next;
            }
            
            while(pHead1 && pHead2) {
                if(pHead1 == pHead2)
                    break;
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
            
            
            return pHead1;
            
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，194人围观）

还没有评论，来说两句吧...

相关阅读

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

输入两个链表，找出它们的第一个公共节点。如下面的两个链表： ![824defb1aa1ffafff732355117d10e00.png][] 在节点 c1 开始相交。

一时失言乱红尘/ 2024年03月29日 14:22/ 0 赞/ 72 阅读

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

题目：剑指 Offer 52. 两个链表的第一个公共节点，哈哈，我们今天来看一道很简单的题嘛，这是选自剑指 Offer 上的一道题，好了，我们一起来看看题意吧：考虑到直

Dear 丶/ 2023年09月27日 12:31/ 0 赞/ 123 阅读

相关剑指offer |52. 两个链表的第一个公共节点

题目： > 输入两个链表，找出它们的第一个公共节点。 > > 如下面的两个链表： > ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5na

快来打我*/ 2022年12月29日 14:10/ 0 赞/ 169 阅读

相关《剑指Offer》52：两个链表的第一个公共节点

题目输入两个链表，找出它们的第一个公共节点。 public static class ListNode{ public int val;

た入场券/ 2022年12月11日 15:27/ 0 赞/ 141 阅读

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

题目输入两个链表，找出它们的第一个公共节点。如下面的两个链表： ![在这里插入图片描述][20201102205737962.png_pic_center]

亦凉/ 2022年11月22日 00:04/ 0 赞/ 159 阅读

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

2021-07-21 LeetCode每日一题链接：[https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di

待我称王封你为后i/ 2022年08月31日 00:46/ 0 赞/ 149 阅读

相关剑指offer----两个链表的第一个公共节点----java实现

输入两个链表，找出它们的第一个公共结点。思路：两个有公共节点的链表，具有这样的特点：单向链表的节点的的属性有节点的值，它指向的下一个节点。所以当有一个公共节点时，不仅值

快来打我*/ 2022年07月20日 15:11/ 0 赞/ 148 阅读

相关剑指offer-题37：两个链表的第一个公共节点

题目描述输入两个链表，找出它们的第一个公共结点。实验平台：[牛客网][Link 1] -------------------- 解决思路：这题书上列举了

超、凢脫俗/ 2022年05月27日 02:40/ 0 赞/ 171 阅读

相关剑指Offer-两个链表的第一个公共节点

一、题目：两个链表的第一个公共节点 > 题目：输入两个链表，找出它们的第一个公共结点。　　链表结点定义如下，这里使用C\语言描述： ![复制代码][copycode

待我称王封你为后i/ 2022年05月23日 09:41/ 0 赞/ 231 阅读

相关剑指offer:两个链表的第一个公共节点

题目描述输入两个链表，找出它们的第一个公共结点。 AC C++ Solution: 思路: 因为第一个公共节点后面所有的节点都相同,首先计算两链表的长度差,抹平长度

港控/mmm°/ 2022年04月10日 09:13/ 0 赞/ 195 阅读