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

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

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 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

39110
来自专栏Android知识点总结

Java总结之映射家族--Map概览

774
来自专栏拭心的安卓进阶之路

Java 集合深入理解(17):HashMap 在 JDK 1.8 后新增的红黑树结构

上篇文章我们介绍了 HashMap 的主要特点和关键方法源码解读,这篇文章我们介绍 HashMap 在 JDK1.8 新增树形化相关的内容。 传统 HashMa...

2856
来自专栏小二的折腾日记

剑指offer-刷题总结

分析:由于每一行都有递增的特性,我们可以采用类似二分搜索的方法。将数组分成行列来进行搜索。

1021
来自专栏Android知识点总结

Java容器源码攻坚战--第三战:HashMap(一)

HashMap怪复杂的,如果一开始就上网上一大堆的HashMap的元素图,也没什么太大意思。 这里从一个小测试开始说起,一步步debug在HashMap里走一...

645
来自专栏海天一树

约瑟夫环的三种解法

约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法...

842
来自专栏和蔼的张星的图像处理专栏

452. 删除链表中的元素基本操作。链表

删除链表中等于给定值val的所有节点。 样例 给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2...

631
来自专栏赵俊的Java专栏

镜像二叉树

1173
来自专栏格子的个人博客

Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

JDK1.8之前,HashMap并没有采用红黑树,所以哈希桶上的链表过长时,就会有效率问题。

554
来自专栏java一日一条

经典数据结构和算法回顾

最近想回过头来看看以前写的一些代码,可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录,后面也没再遇到相同的问题,忘的都差不多了。只能勉...

401

扫码关注云+社区