LeetCode ——160. 相交链表,142. 环形链表 II

✅<1>主页:C语言的前男友
📃<2>知识讲解:LeetCode经典链表笔试题目
🔥<3>创作者:C语言的前男友
☂️<4>开发环境:Visual Studio 2022
🏡<5>系统环境:Windows 10
💬<6>前言:今天来讲解几个经典的链表题目,链接已经给出大家可以挑战一下。

人脸核身接口

目录

魔百盒固件

160. 相交链表

progressbar

题目链接:160. 相交链表

版本号详解

题目描述:

前端练手项目合集

 思路一:

高考

代码:

dos

思路二:

婚礼

代码:

ios上架苹果商店流程

142. 环形链表 II

实习

题目链接:142. 环形链表 II

频域

题目描述:

DOM

思路一:

双目标定

 代码:

手机拍照旋转问题

思路二:

YOLOv5

代码:

安全

 最后:成为自己想成为的样子,才能得到自己想得到的东西。

cglib静态代理


160. 相交链表

题目链接:160. 相交链表

题目描述:

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。图示两个链表在节点 c1 开始相交

自动化测试的持续集成

mock工具

 思路一:

如果两个链表相交,则必有公共结点,我们只需要返回第一个公共结点就可以了,第一个公共结点就是第一个相交结点。怎么找他的第一个公共结点呢?最简单的就是两个循环,去遍历两个链表。用链表B中的结点挨个与链表A的结点比较是否相等。如果存在相等的结点,第一个相等的结点就是两个单链表相交的起始节点,返回任意一个结点。如果没有相交结点,那么两个链表不相交,返回 NULL 。此方法时间复杂度为O(n^2).

uniapp

代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    for(struct ListNode*i=headA;i!=NULL;i=i->next)
    {
        for(struct ListNode*j=headB;j!=NULL;j=j->next)
        {
            if(i==j)
            {
                return i;
            }
        }
    }
    return NULL;
}

思路二:

如果让两个指针能从下面的地方开始走,那么两个指针相遇的时候一定就是两个单链表相交的起始节点。

ios解锁大师有用吗

火车票查询系统

 那么问题就是怎么找到这两个位置。其实不难发现只要让 curB 先走,让 curB 之后的链表节点数与 curA 后面的节点数一样。只要让长的链表先走 长链表比短链表多的节点数的 步数,就可以了。

应用开发

代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*listA=headA;
    struct ListNode*listB=headB;
    int countA=0; //A链表的长度
    int countB=0; //B链表的长度
    //计算B链表的长度
    while(listA) 
    {
        countA++;
        listA=listA->next;
    }
    //计算A链表的长度
    while(listB)
    {
        countB++;
        listB=listB->next;
    }
    //计算长度差
    int n=abs(countA-countB);
    //先假设A为长链表,B为短炼表
    struct ListNode*longlist=headA;
    struct ListNode*shortlist=headB;
    //如果不符合就纠正一下
    if(countB>countA)
    {
        longlist=headB;
        shortlist=headA;
    }
    //让长链表先走
    while(n--)
    {
        longlist=longlist->next;
    }
    //长短链表同时走
    while(longlist&&shortlist)
    {
        //第一次相遇就是相交的第一个结点
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return NULL;
}

142. 环形链表 II

题目链接:142. 环形链表 II

题目描述:

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表。

vue-cli

Java锁

 

android tv

armbian

思路一:

利用带环链表的特点加上严格的逻辑推导:

节日

比特币

 代码:

struct ListNode *detectCycle(struct ListNode *head){

    struct ListNode*frist=head;//快指针
    struct ListNode*slow=head;//慢指针
    //如果遇到结点为空,就说明不是带环结点,直接返回NULL
    while(frist&&frist->next)
    {
        frist=frist->next->next; //快指针一次走两步
        slow=slow->next; //慢指针一次走一步
        if(frist==slow)//在环中相遇
        {
            struct ListNode*meet=frist;//一个从环中走
            struct ListNode*cur=head;//一个从链表头走
            while(meet!=cur)//相遇是循环结束
            {
                meet=meet->next;
                cur=cur->next;
            }
            return meet;//相遇的结点就是环入口点
        }
    }
    return NULL;

}

思路二:

利用快慢指针,让两指针在环中相遇点,将相遇点拆开。相遇点的后一个结点变成新的头节点,相遇点的next指向NULL。这样带环问题就变成了,两个链表相交的问题。

图像处理

产生的两条新的链表,head 和 phead  ,两条链表相交的第一个的以公共结点就是,以前带环链表的环入口处。

代码:

//找到链表相交的第一个结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*listA=headA;
    struct ListNode*listB=headB;
    int countA=0;
    int countB=0;
    while(listA)
    {
        countA++;
        listA=listA->next;
    }
    while(listB)
    {
        countB++;
        listB=listB->next;
    }
    int n=abs(countA-countB);
    struct ListNode*longlist=headA;
    struct ListNode*shortlist=headB;
    if(countB>countA)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(n--)
    {
        longlist=longlist->next;
    }
    while(longlist&&shortlist)
    {
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return NULL;
}
struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode*frist=head;
    struct ListNode*slow=head;
    while(frist&&frist->next)
    {
        frist=frist->next->next;
        slow=slow->next;
        //快慢指针在环中相遇
        if(frist==slow)
        {
            //拆分环行链表段
            struct ListNode*phead=frist->next;
            slow->next=NULL;
            //返回相交结点
            return getIntersectionNode(phead,head);
        }
    }
    return NULL;
}

 最后:成为自己想成为的样子,才能得到自己想得到的东西。

 

 

 

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注