算法-寻找两个链表的第一个公共结点

题目: 输入两个链表,找到他们的第一个公共结点,链表结点定义如下:

struct ListNode
{
  int value;
  ListNode *next;
};

解题思路: 首先我们需要想清楚的是,如果一个链表出现了公共结点,那么这两个链表是什么样子的,显然它的结构应该是一个“Y”型:

由于是单向链表,所以只有一个指向下一个结点的指针。这意味着如果出现了公共结点那么这个结点之后的结点也一定是公共的,这也是为什么题目强调了第一个结点,也就是说永远不会有这样的情况:

我当然可以通过最简单的方法实现这个任务,就是链表1走一步后遍历链表2,这样的话时间复杂度将是O(mn),我们当然希望有一种方法可以只遍历一遍链表就找到这个结点,但是这有一个重要前提: 同时遍历两个链表,想要找到公共的结点就必须要在某一次循环中两个链表同时到达这个结点,比如第一张图中的要找的结点是5,那么在某次循环中用链表2的结点4和链表1的结点5比较,那么永远不可能找到公共结点。 所以这就需要在同时遍历前做一些准备工作,好在“Y”型的结构让这个工作变得很容易,那就是让长的链表先走几步,这个思想在获取链表中倒数第k个结点也有体现,比如链表1长度是m,链表2长度是n(m>n),公共的结点个数是k,那么链表1非公共的结点个数为m-k,链表2非公共的结点个数为n-k。那么走的步数就确定了:(m-k)-(n-k)=m-n,前提条件是先获取两个链表的长度。

在上面的图中,可以让链表1先走两步,之后链表1,2同时走,每走一步就判断一次是否为公共结点。

代码实现:

ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
{

    unsigned int nLength1 = GetListLength(pHead1);
    unsigned int nLength2 = GetListLength(pHead2);
    int nLengthDif = nLength1 - nLength2;

    ListNode* pListHeadLong = pHead1;
    ListNode* pListHeadShort = pHead2;
    if(nLength2 > nLength1)
    {
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
        nLengthDif = nLength2 - nLength1;
    }

    for(int i = 0; i < nLengthDif; ++ i)
        pListHeadLong = pListHeadLong->next;

    while((pListHeadLong != NULL) && 
        (pListHeadShort != NULL) &&
        (pListHeadLong != pListHeadShort))
    {
        pListHeadLong = pListHeadLong->next;
        pListHeadShort = pListHeadShort->next;
    }

    ListNode* pFisrtCommonNode = pListHeadLong;

    return pFisrtCommonNode;
}

unsigned int GetListLength(ListNode* pHead)
{
    unsigned int nLength = 0;
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        ++ nLength;
        pNode = pNode->next;
    }

    return nLength;
}

代码还是很好理解的,其中有一点是判断公共结点的条件:pListHeadLong == pListHeadShort,这个条件并没有对比链表结点中的value,而是直接比较的指针,如果是公共结点的话,显然两个指针指向的是同一个内存地址。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【C++练手】C++实现单链表

前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作。 链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺...

3297
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2306
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

40711
来自专栏猿人谷

查找链表中倒数第k个结点

题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下: struct ListNode { in...

1955
来自专栏算法与数据结构

数据结构 栈&队列

2-4 依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( ) 删除,移动头指针; 增加,移动尾指针; 删除a,b ,...

31510
来自专栏尾尾部落

[LeetCode]Valid Parentheses 验证括号是否有效闭合 [LeetCode]Valid Parentheses 验证括号是否有效闭合

链接:https://leetcode.com/problems/valid-parentheses/#/description 难度:Easy 题目:...

713
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题37两个链表的第一个公共结点

本题的详细解析均在代码注释中: import java.util.Stack; /** * 题目:输入两个链表,找出他们的第一个公共结点 * @autho...

2905
来自专栏Petrichor的专栏

tensorflow编程: Inputs and Readers

与 tf.placeholder 不同的是,这里如果 未 被feed_dict,并不会 打印报错,而是打印出 默认数据。

873
来自专栏文武兼修ing——机器学习与IC设计

栈与栈的实现栈栈的基本操作栈的实现

栈 栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作...

2735
来自专栏進无尽的文章

编码篇-数组的相关使用

数据的常规方法的使用本文不做描述,本文旨在归纳一些数组不是很常用的方法使用。算作一个归纳笔记,后续会持续更新.....

842

扫码关注云+社区