算法学习-链表-level2-两个链表的第一个公共节点

这篇具有很好参考价值的文章主要介绍了算法学习-链表-level2-两个链表的第一个公共节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

输入两个链表,找出它们的第一个公共节点,如图两个链表从C1开始相交

算法学习-链表-level2-两个链表的第一个公共节点,算法,学习,链表

1、哈希与集合

实现思路:将第一个链表的所有节点存入集合中,遍历第二个链表,并在集合中查询链表二的节点是否出现过

实现代码:

struct ListNode* getInteractionNode_hash(struct ListNode* headA, struct ListNode* headB)
{
    set<ListNode*> st;
    while (headA != NULL) {
        st.insert(headA);
        headA = headA->next;
    }
    while (headB != NULL) {
        if (st.count(headB) !=  0)return headB;
        headB = headB->next;
    }
    return NULL;
}

 

2、使用栈

实现思路:根据题意可知在相同节点之后,两链表的节点完全相同,这里我们可以利用栈结构后进先出的特点来实现这一题,分别将两链表存储栈内,同时取出栈顶元素进行对比,当遇到不同节点之后返回上一节点(prev)

实现代码:

struct ListNode* getInteractionNode_stack(struct ListNode* headA, struct ListNode* headB)
{
    stack<ListNode*>stkA, stkB;
    while (headA != NULL) {
        stkA.push(headA);
        headA = headA->next;
    }
    while (headB != NULL) {
        stkB.push(headB);
        headB = headB->next;
    }
    ListNode* prevA = NULL, *prevB = NULL;
    while (stkA.size() != 0 && stkB.size() != 0) {
        ListNode* currA = stkA.top();
        stkA.pop();
        ListNode* currB = stkB.top();
        stkB.pop();
        if (currA != currB)break;
        prevA = currA;
        prevB = currB;
    }
    return prevA;
}

3、补差法

实现思路:在两链表大小相同时,我们完全可以使用循环的方式逐个判断两链表节点是否相同。所以,遵循这一思路衍生出了两种方法:补差法和拼接法。这里我们先介绍补差法,补差法顾名思义,将两个不同长度的链表的长度差补上。这里的补指的是在循环判断节点相同之前提前移动较长链表的节点,保证后续对比可以同步进行。因为两链表之前的节点全部不相同,所以可以很放心的移动节点。进而完成问题。

实现代码

struct ListNode* getInteractionNode_sub(struct ListNode* headA, struct ListNode* headB)
{
    if (headA == NULL || headB == NULL)return NULL;
    ListNode *currA = headA, *currB = headB;
    int la = 0, lb = 0;
    while (currA != NULL) {
        ++la;
        currA = currA->next;
    }
    while (currB != NULL) {
        ++lb;
        currB = currB->next;
    }
    int sub = la > lb ? la - lb : lb - la;
    currA = headA;
    currB = headB;
    if (la > lb)
    {
        int cnt = 0;
        while (cnt < sub) {
            ++cnt;
            currA = currA->next;
        }
    }
    if (lb >la) {
        int cnt = 0;
        while (cnt < sub) {
            ++cnt;
            currB = currB->next;
        }
    }
    while (currA != currB) {
        currA = currA->next;
        currB = currB->next;
    }
    return currA;
}

4、双指针法

实现思路:我们为了解决两链表长度不等的问题,衍生出了双指针法(拼接法)。在这里我们可以将理解链表理解成两部分,不同部分(Left)和相同部分(Right)。导致两链表长度不相同的部分为Left部分,这里我们可以利用拼接的方式处理这个问题。

 先看下方链表:

A :1 2 3 4 5

B :7 5 4 5

拼接AB与BA

AB :1 2 3 4 5 7 5 4 5

BA :7 5 4 5 1 2 3 4 5

不难发现AB与BA尾部完全相同,这里的尾部就是两链表相同部分(Right)

如果用公式表达出两链表的内容可以得到

AB = Left(A) + Right(A) + Left(B) + Right(B)

BA = Left(B) + Right(B) + Left(A) + Right(A)

根据定义理解Right(A)= Right(B)

Left(A) + Right(A) + Left(B) = Left(B) + Right(B) + Left(A)恒成立

算法学习-链表-level2-两个链表的第一个公共节点,算法,学习,链表

所以对于长度不同的链表可以使用拼接的方法使其总长度相同,进而使其可以比较。

在代码实现方面,我们并不需要直接将两链表拼接,只需要在链表循环至NULL时再从另一个链表开始遍历即可,这里就完成了进一步优化。

代码实现 

struct ListNode* getInteractionNode_connect(struct ListNode* headA, struct ListNode* headB)
{
    if (headA == NULL || headB == NULL)return NULL;
    ListNode *currA = headA, *currB = headB;
    while (currA != currB) {
        currA = currA->next;
        currB = currB->next;
        //在拼接后遍历结束时 currA == currB一定成立
        //防止两链表完全不同导致死循环 给予null出口 
        if (currA != currB) {
            //两链表长度不同 第一次遍历结束时候
            if (currA == NULL) {
                currA = headB;
            }
            if (currB == NULL) {
                currB = headA;
            }
        }
    }
    return currA;
}

你变成我,走过我走过的路。
我变成你,走过你走过的路。
然后我们便相遇了..  

——leetcode

希望对大家能有所帮助。

图片来源:编程导航算法通关村第一期

具体来源:算法通关村第一关——链表—白银挑战

作者:余秋文章来源地址https://www.toymoban.com/news/detail-640786.html

到了这里,关于算法学习-链表-level2-两个链表的第一个公共节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包