【LeetCode】【数据结构】单链表OJ常见题型(二)

这篇具有很好参考价值的文章主要介绍了【LeetCode】【数据结构】单链表OJ常见题型(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode】【数据结构】单链表OJ常见题型(二),LeetCode刷题笔记,数据结构,leetcode,数据结构,算法,c语言,c++

 👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言:

【LeetCode】面试题02.04. 分割链表

【LeetCode】160. 相交链表

【LeetCode】141. 环形链表

【LeetCode】142. 环形链表Ⅱ

方法一

方法二 


前言:

本系列博文博主会讲解链表的经典OJ题目。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码:🌟fanfei_c的仓库🌟

=========================================================================

【LeetCode】面试题02.04. 分割链表

原题链接:🍏分割链表🍏

题目:给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

【LeetCode】【数据结构】单链表OJ常见题型(二),LeetCode刷题笔记,数据结构,leetcode,数据结构,算法,c语言,c++

本题使用带头结点的单链表更为简单,可以免去极端情况的判断(全大于等于x或全小于x)以及连接两个链表时的麻烦。

所以我们直接申请两个哨兵结点。

  • 令小于x的尾插到lead的链表上;
  • 令大于或等于x的尾插到ghead的链表上。

最后连接两个链表即可。

代码实现: 

struct ListNode* partition(struct ListNode* head, int x)
{
    struct ListNode* ghead,*gtail,*lhead,*ltail;
    struct ListNode* cur=head;

    ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));

    while(cur)
    {
        if(cur->val<x)
        {
            ltail->next=cur;// 尾插
            ltail=ltail->next;
        }
        else
        {
            gtail->next=cur;// 尾插
            gtail=gtail->next;
        }
        cur=cur->next;
    }

    gtail->next=NULL;// 不置空 会导致链表进入循环

    ltail->next=ghead->next;// 连接两个链表

    struct ListNode* newhead=lhead->next;// 保存返回值,以便释放与返回
    free(lhead);
    free(ghead);

    return newhead;
}

【LeetCode】160. 相交链表

原题链接:🍏相交链表🍏

题目:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

【LeetCode】【数据结构】单链表OJ常见题型(二),LeetCode刷题笔记,数据结构,leetcode,数据结构,算法,c语言,c++

该题可以利用差距步的方法,首先计算两个链表的长度,利用该长度差让长的链表先走差距步。

再同时向后走,当两个指针相等时,该位置即为交点。

代码中的假设法是一种非常值得学习的方法,大家可以自行领悟,我在代码中标识出来了。

代码实现:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;

    int numA=1;
    int numB=1;
    while(curA->next)// 题目给定链表不为空,且两个循环结束后我们需要利用cur指针来判断是否相交,所以这里采用cur->next来判断结束
    {
        curA=curA->next;
        numA++;// 由于上面循环结束条件为cur->next为空,所以这里的值少1。因此我们定义num的值为1
    }

    while(curB->next)// 同上
    {
        curB=curB->next;
        numB++;// 同上
    }

    if(curA!=curB)// 不相交
    {
        return NULL;
    }

    struct ListNode* longList=headA,*shortList=headB;
    int gap=abs(numA-numB);// 计算差距步,abs绝对值函数
    if(numA<numB)// 假设法
    {
        longList=headB;
        shortList=headA;
    }

    while(gap--)// 令longList走差距步
    {
        longList=longList->next;
    }

    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }
    return longList;
}

【LeetCode】141. 环形链表

原题链接:🍏环形链表🍏

题目:给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

【LeetCode】【数据结构】单链表OJ常见题型(二),LeetCode刷题笔记,数据结构,leetcode,数据结构,算法,c语言,c++

快慢指针法: 

定义两个指针。

  • 一个名为slow,slow每次走一步;
  • 一个名为fast,fast每次走两步。

当fast或者fast->next不为空时持续进行指针移动。

如果该链表为环形链表,那么一定存在某一时刻slow与fast相等,返回true;

如果跳出循环证明链表为非环形链表。

代码实现:

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* slow=head;
    struct ListNode* fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
            return true;
    }
    return false;
}

 【LeetCode】142. 环形链表Ⅱ

原题链接:🍏环形链表Ⅱ🍏

题目:给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

方法一

与上面的思路相同,同样需要首先找到快慢指针相遇的时刻。

因为slow在一圈内必然fast会与其相遇,所以设slow在环内走了X距离。

设环外链表长度L,环的周长为C,slow进环时fast已经走了n圈,fast走的距离是slow走的距离的二倍,我们可以得到2(L+X)=L+n*C+X,即L=(n-1)*C+C-X。

如图:

【LeetCode】【数据结构】单链表OJ常见题型(二),LeetCode刷题笔记,数据结构,leetcode,数据结构,算法,c语言,c++

结论:一个指针在相遇点meet,另一个指针为头指针,两指针同时移动,会在入环点相遇。

代码实现: 

struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            while (head != meet)
            {
                meet = meet->next;
                head = head->next;
            }
            return head;
        }
    }
    return NULL;
}

 方法二 

还记得上面的题目相交链表么?

我们可以将该环在相遇点meet处断开,再执行判断相交链表的函数即可。

代码实现:

//相交链表
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;

    int numA = 1;
    int numB = 1;
    while (curA->next)// 题目给定链表不为空,且两个循环结束后我们需要利用cur指针来判断是否相交,所以这里采用cur->next来判断结束
    {
        curA = curA->next;
        numA++;// 由于上面循环结束条件为cur->next为空,所以这里的值少1。因此我们定义num的值为1
    }

    while (curB->next)// 同上
    {
        curB = curB->next;
        numB++;// 同上
    }

    if (curA != curB)// 不相交
    {
        return NULL;
    }

    struct ListNode* longList = headA, * shortList = headB;
    int gap = abs(numA - numB);// 计算差距步,abs绝对值函数
    if (numA < numB)// 假设法
    {
        longList = headB;
        shortList = headA;
    }

    while (gap--)// 令longList走差距步
    {
        longList = longList->next;
    }

    while (longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}

//环形链表Ⅱ
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            struct ListNode* newhead = meet->next;
            meet->next = NULL;

            return getIntersectionNode(head, newhead);
        }
    }
    return NULL;
}

快慢指针法是链表解题思路中非常常见的一种方法,博主在该系列博文的上一篇文章中也利用了该种方法,可以供大家整理参考,消化思路。

链接在这👉【LeetCode】【数据结构】单链表OJ常见题型(一)👈


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

========================================================================= 文章来源地址https://www.toymoban.com/news/detail-624110.html

到了这里,关于【LeetCode】【数据结构】单链表OJ常见题型(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构--单链表OJ题

    上文回顾---单链表 这章将来做 一些链表的相关 题目 。 目录 1.移除链表元素 2.反转链表 3.链表的中间结点 4.链表中的倒数第k个结点 5.合并两个有序链表 6.链表分割 7.链表的回文结构 8.相交链表 9.环形链表 ​编辑  10.环形链表II ​编辑 ​编辑    思路:我们可以 通过循环链

    2024年02月14日
    浏览(80)
  • 【数据结构】单链表OJ题

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️ 感谢大家点赞👍收藏⭐评论✍️ 目录 一、移除链表元素 💡方法一: 💡方法二: 二、链表的中间节点 💡方法一: 三、链表中倒数第k个结点 💡方法一: 四、反转链表 💡方法一:

    2024年02月14日
    浏览(56)
  • 【数据结构】单链表OJ题(一)

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️ 感谢大家点赞👍收藏⭐评论✍️ 目录 一、移除链表元素 💡方法一: 💡方法二: 二、链表的中间节点 💡方法一: 三、链表中倒数第k个结点 💡方法一: 四、反转链表 💡方法一:

    2024年02月13日
    浏览(78)
  • 【数据结构】单链表OJ题(二)

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退  ❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、链表分割 💡方法一: 二、链表的回文 💡方法一:  三、相交链表 💡方法一:  四、环形链表  💡方法一:  🗒️前言: 在上一期中我们

    2024年02月14日
    浏览(38)
  • 数据结构——单链表OJ题(第二弹)

    此次练习题有两道! 有点小难度,但相信难不住大家的! 我也会给出两道OJ题的链接,大家也赶快去试一试吧 题目链接: OJ链接 提示: 链表中节点的数目范围在范围 [0, 104] 内 -105 = Node.val = 105 pos 的值为 -1 或者链表中的一个有效索引 本题有两个解析思路~ 代码演示: 提示:

    2024年02月14日
    浏览(38)
  • 【数据结构练习】单链表OJ题(二)

    题目: 示例: 注意:不能根据节点的值来比较是否相交,而是根据节点在内存中是否指向相同的位置。 例如以上图: 链表A:4、1、8、4、5 链表B:5、6、1、8、4、5 链表A和链表B都有节点的值为1,但是它们在内存中指向不同的位置,而值为8的节点(A的第三个节点、B的第四个

    2024年02月11日
    浏览(39)
  • 【数据结构练习】单链表OJ题(一)

    题目: 思路1: 在原来的链表上进行修改,节点的数据是val的删除,然后前后再连接起来。 需要考虑的因素: 1.要删除的节点位置在第一个节点; 2.要删除的节点位置在中间任意一个节点; 3.要删除的节点位置在最后一个节点 用一个变量cur遍历链表,要删除的节点是头节点

    2024年02月11日
    浏览(60)
  • 【数据结构】移除链表元素-图文解析(单链表OJ题)

    LeetCode链接:203. 移除链表元素 - 力扣(LeetCode) 本文导航 💭做题思路 🎨画图更好理解: ✍️代码实现 🗂️分情况讨论: ❄️极端情况: 遍历链表,找到值为 val 的节点删除 这里需要两个指针  cur 用来遍历链表  prev 指向 cur 的前一个位置,方便删除一个节点后,链接前

    2024年02月14日
    浏览(33)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(68)
  • 【LeetCode】【数据结构】二叉树必刷OJ题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 【LeetCode】226.翻转二叉树 【LeetCode】100.相同的树 【LeetCode】5.对称二叉树 【LeetCode】9.另一颗树的子树

    2024年02月08日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包