写点什么

算法题学习 --- 两个链表的第一个公共结点

作者:桑榆
  • 2022-11-15
    广东
  • 本文字数:2225 字

    阅读完需:约 7 分钟

题目

描述

输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)

数据范围: 0n≤1000 要求:空间复杂度 O(1),时间复杂度 O(n)

例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示:

可以看到它们的第一个公共结点的结点值为 6,所以返回结点值为 6 的结点。

输入描述:

输入分为是 3 段,第一段是第一个链表的非公共部分,第二段是第二个链表的非公共部分,第三段是第一个链表和第二个链表的公共部分。 后台会将这 3 个参数组装为两个链表,并将这两个链表对应的头节点传入到函数 FindFirstCommonNode 里面,用户得到的输入只有 pHead1 和 pHead2。

返回值描述:

返回传入的 pHead1 和 pHead2 的第一个公共结点,后台会打印以该节点为头节点的链表。

示例 1

输入:{1,2,3},{4,5},{6,7}返回值:{6,7}说明:第一个参数{1,2,3}代表是第一个链表非公共部分,第二个参数{4,5}代表是第二个链表非公共部分,最后的{6,7}表示的是2个链表的公共部分这3个参数最后在后台会组装成为2个两个无环的单链表,且是有公共节点的          
复制代码

示例 2

输入:{1},{2,3},{}返回值:{}说明:2个链表没有公共节点 ,返回null,后台打印{} 
复制代码

分析

思路一---使用 vector 存储链表节点信息

这是比较容易想到的思路,我们使用 vector 存储其中一个链表的节点信息,然后遍历另一个链表,查找当前的节点是否在 vector 中,如果在,说明这是第一个相同的节点,我们直接返回该节点即可,否则等到遍历到链表末尾,返回 nullptr 即可。

但是,明显地,我们存储了 n 个节点的信息,这里的空间复杂度是 O(n),不符合题目的要求。

思路二---使用双指针法

我们先来考虑这样一种特殊的情况,如果两个链表的长度是相同的,且公共节点是第三个,那么我们分别遍历两个链表,那么一定会在第三个节点处相遇。

换言之,有公共节点的链表,它们的后半部分是完全相同的,区别只是前半部分的节点值不同,节点数量不同,上面的特殊情况中链表长度相同,所以我们从头开始遍历可以找到公共节点,那么我们的任务就是让两个遍历指针对齐。

我们可以事先遍历两个链表,得到两个链表的长度差 n,然后较长的链表遍历指针先走 n 步,此时,两个链表的遍历指针就如同遍历两个长度相同的链表了,一起向后遍历就可以找到第一个相同的节点了。如下:

  • step 1:单独的遍历两个链表,得到各自的长度。

  • step 2:求得两链表的长度差 n,其中较长的链表的指针从头先走 n 步。

  • step 3:两链表指针同步向后遍历,遇到第一个相同的节点就是第一个公共节点。

代码示例

版本一

事先占用了 O(n)的空间,在进行查找时,每遍历一个元素都需要查找一次 walkedListNode1,时间复杂度也达到了 O(mn),这种思路比较容易想到,但消耗资源比较大。

/*struct ListNode {        int val;        struct ListNode *next;        ListNode(int x) :                        val(x), next(NULL) {        }};*/class Solution {public:    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {                std::vector<ListNode*> walkedListNode1;
while(nullptr != pHead1){ walkedListNode1.push_back(pHead1); pHead1 = pHead1->next; }
while(nullptr != pHead2){ auto iter = std::find(walkedListNode1.begin(),walkedListNode1.end(),pHead2); if(iter != walkedListNode1.end()){ return pHead2; } pHead2 = pHead2->next; } return pHead2; }};
复制代码

版本二

注意 pQuick 指较长的链表,pSlow 指较短的链表,pQuick 需要提前走 abs(length1 - length2)步。

全程只使用了 pQuick 和 pSlow 两个指针,时间上也是 O(n),遍历链表的时间。

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :            val(x), next(NULL) {    }};*/class Solution {  public:    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {        int length1 = GetLinkListLength(pHead1);        int length2 = GetLinkListLength(pHead2);
ListNode* pSlow = pHead1; ListNode* pQuick = pHead2; if (length1 > length2) { pSlow = pHead2; pQuick = pHead1; }
// pQuick walk abs(length1 - length2) for (int i = 0; i < abs(length1 - length2); ++i) { pQuick = pQuick->next; }
// pQuick and pSLow walk together find the first same node while (nullptr != pQuick) { if (pQuick == pSlow) { return pQuick; } pQuick = pQuick->next; pSlow = pSlow->next; } return pQuick; }
int GetLinkListLength(ListNode* pList) { int length = 0; while (nullptr != pList) { length++; pList = pList->next; } return length; }};
复制代码


发布于: 刚刚阅读数: 4
用户头像

桑榆

关注

北海虽赊,扶摇可接;东隅已逝,桑榆非晚! 2020-02-29 加入

Android手机厂商-相机软件系统工程师 爬山/徒步/Coding

评论

发布
暂无评论
算法题学习---两个链表的第一个公共结点_算法题_桑榆_InfoQ写作社区