剑指offer面试题[37]-两个链表的第一个公共结点

电玩女神 2022-06-11 01:23 114阅读 0赞

## 题目描述 ##

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

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };
    */
    //思路：
    //如果两个链表有公共结点，那么两个第一个公共结点后面的结点都是相同的，若链表1的长度比链表2的长度大len，
    //则需要将链表1起始结点向后移动len个长度，确保两个链表初始比较结点后面的长度是一样的。
    
    //链表的初始化其实就是链表的创建的过程，它的初始化其实和变量、
    //指针的初始化一样，如果你定义了一个指针，而没有对其进行初始化，
    //这个指针就是一个“野指针”，指向一块垃圾内存，这是很危险的，
    //链表的初始化就是为了让程序员能够获取链表的首地址，然后对其进行插入、删除、排序等操作了！
    
    class Solution {
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            int len,len1,len2;
            ListNode* res=NULL;  //初始化一个链表让其为空
            if(pHead1==NULL||pHead2==NULL)   //若两个链表有一个为空，则返回空链表res  
                return res;               
            ListNode* pNode1=pHead1;    //这里很重要，计算原始两个链表的长度时，不能在原始的结点上操作
            ListNode* pNode2=pHead2;
            while(pNode1!=NULL)    //计算pHead1的长度
                {
                   ++len1;
                   pNode1=pNode1->next;
                }
            while(pNode2!=NULL)     //计算pHead2的长度
                {  ++len2;
                   pNode2=pNode2->next;
                }
            len=(len1>len2)?(len1-len2):(len2-len1);  //pHead1与pHead2的长度差len
            if(len1>len2)             //这里的意思是，如果pHead1的长度大于pHead2的长度，将pHead1往后移动len
              {
                for(int i=0;i<len;i++)
                   pHead1=pHead1->next;
              }
            else                     //如果pHead2的长度大于pHead1的长度，将pHead2往后移动len
              {
                for(int i=0;i<len;i++)
                   pHead2=pHead2->next;
              }
            while(pHead1!=NULL&&pHead2!=NULL)  
              {
                if(pHead1->val!=pHead2->val)   //不相等，pHead1和pHead2分别往后移动一个长度
                 {
                   pHead1=pHead1->next;
                   pHead2=pHead2->next;
                 }
                 else             //相等，将结果赋给res，并结束while循环
                 {
                   res=pHead1;
                   break; 
                 }
              }
            return res;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关【剑指offer-Java版】37两个链表的第一个公共结点

两个链表中的第一个公共顶点：解法一：两次遍历即可第一次遍历找到两个链表的长度，求出差值k，然后较长的；链表先走k步，之后两个链表同时走，直到遇到第一个相同的结点为止

梦里梦外;/ 2022年08月21日 09:48/ 0 赞/ 93 阅读

相关剑指offer面试题求两个链表的第一个公共结点

题目描述：输入两个链表，找出它们的第一个公共结点。链表结点定义如下： struct ListNode \{ int 　　　　m\_nKey; List

悠悠/ 2022年07月28日 09:00/ 0 赞/ 99 阅读

相关剑指offer之面试题37两个链表的第一个公共结点

问题描述：输入两个链表，找出他们的第一个公共结点。实现代码如下： include <stdio.h> include <stdlib.h> i

男娘i/ 2022年07月24日 04:04/ 0 赞/ 117 阅读

相关剑指Offer面试题37（Java版）：两个链表的第一个公共结点

题目：输入两个链表，找出它们的第一个公共结点。面试的时候碰到这道题，很多应聘者的第一反应就是蛮力法：在第一链表上顺序遍历每个结点，没遍历到一个结点的时候，在第二个链表上顺序

绝地灬酷狼/ 2022年07月16日 06:13/ 0 赞/ 88 阅读

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

1.题目描述输入两个链表，找出它们的第一个公共结点。 2.分析如果两个链表有公共节点，那么这两条链表从该公共节点开始往后的部分是重合的。方法1：可

左手的ㄟ右手/ 2022年06月15日 01:16/ 0 赞/ 139 阅读

相关剑指offer面试题[37]-两个链表的第一个公共结点

题目描述输入两个链表，找出它们的第一个公共结点。 / struct ListNode { int val; struct List

电玩女神/ 2022年06月11日 01:23/ 0 赞/ 115 阅读

相关剑指Offer | 两个链表的第一个公共结点

一、题目输入两个链表，找出它们的第一个公共结点。二、思路 (1) 两个链表是单向链表，如果两个链表有公共节点，那么这两个链表从某一节点开始，它们的Next都指

谁借莪１个温暖的怀抱￠/ 2022年05月23日 05:49/ 0 赞/ 140 阅读

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

题目描述输入两个链表，找出它们的第一个公共结点。解题思路—长度长的链表先走：看完题目首先要明确一点，如果链表中存在公共结点，则链表尾一定是一样的！所以可以先找出2

r囧r小猫/ 2022年02月19日 05:21/ 0 赞/ 179 阅读

相关 37.两个链表的第一个公共结点《剑指Offer》(Java版)

题目描述 > 输入两个链表，找出它们的第一个公共结点。 import java.util.HashSet; /

谁践踏了优雅/ 2022年01月30日 13:25/ 0 赞/ 138 阅读

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

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述输入两个链表，找出它们的第一个公共结点。结点定义如下： struct ListNod

刺骨的言语ヽ痛彻心扉/ 2021年11月05日 20:32/ 0 赞/ 226 阅读