秋刀鱼在做梦

这个屌丝很懒，什么也没留下！

热门标签

链舞算法谱---链表经典题剖析

作者：秋刀鱼在做梦 | 2024-08-06 12:11:43

踩

链舞算法谱---链表经典题剖析

前言：探究链表算法的奥秘，解锁编程新世界！

欢迎来到我的链表算法博客，这将是您深入了解链表算法，提升编程技能的绝佳机会。链表作为数据结构的重要成员之一，其动态性和灵活性在实现某些功能上发挥不可替代的功效。

本篇博客致力于揭秘链表算法的奥妙，分享实用的学习经验，仅供个人参考。我也希望您能独立实现代码完成相关的题型，还要尝试一题多解，发散思维。

如果对您有帮助，希望您能点赞关注作者，作者会持续输出新鲜干货，尽请期待！

前面，我们学习单链表的基本实现，比如链表的创建，销毁，增删查改等。

如果您不是很了解单链表的相关操作，可以读一下鄙人的单链表博客，或者自行学习。

数据结构篇其二---单链表（C语言+超万字解析）-CSDN博客

我们要注重理论实践结合，阅读他人的代码和相关题解（力扣网站每道题都有大佬（官方）的优秀题解供我们学习），更能熟悉掌握链表的核心知识。

本期精选链表算法的高级话题，选自力扣网站（后面附带刷题链接）。如反转链表，环形链表检测，链表相交，合并有序链表，移除链表元素，分割链表等一系列好题。

编程语言：C语言。

学习方法：

学习数据结构要多画图分析，一步一步来，能积微者速成。

一切条件判断，循环条件不知道怎么写的情况，都是因为图没有画清楚，逻辑没捋清楚。自己动手画比脑补来的快。

前言：探究链表算法的奥秘，解锁编程新世界！

思路一：（双指针法）直接删除值为val的节点。

思路二：数组（换种数据结构）+双指针（对撞指针）

一、反转链表（简单）

据说这是面试出镜率最高的链表题。

206. 反转链表 - 力扣（LeetCode）

这里提供了三组示例供我们实际测试代码。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    
}

代码通过注释的方式给了我们结构体的声明，接着让我们实现函数内部的逻辑。

先分析函数和返回类型吧。

返回值：struct ListNode* 结构体指针，这里返回反转链表后的头指针。

函数参数：就一个参数，传入源链表的头指针。

下面提供几种思路。

思路一：（三指针法）取节点头插。

链表的元素是节点。我们就有第一种想法，将每个节点一个一个取下来进行头插。

同时考虑多种情况不符合人脑逻辑，我们先考虑第一种示例，再完善整体的逻辑。

怎么做呢？先分析已知指针的指向。

只有一个头指针指向链表的第一个节点。我们要实现把节点依次取下来进行头插的操作。显然只有头指针是不够的，我们再创建节点（结构体）指针。

那么创建几个结构体指针呢？

首先，我们处理链表问题，不会轻易动用头指针，除非链表的第一个节点改变了，才需要改变头指针指向。

所以要第一个头指针prev。如下图：

这样有了prev也指向第一个节点，就不要动head指针遍历链表了。

那么如何一个节点指针够了吗？

还是回归到问题上，我们要取下每个节点进行头插。

请阅读下面的代码和观察下面的图


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。
}

很遗憾只通过prev指针把第一个节点取下来了，但是第二个节点的位置找不到了。起不到头插的作用。

所以还需要个next的节点指针，指向取下节点的下一个节点。


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。
 
    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。
}

取第二个节点的情况


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。
 
    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。
 
    //取第二个节点
    prev = next;//先让prev指向原链表的第二个节点。
    next = prev->next;//代码同取下第一个节点的情况。
    prev->next = NULL;
 
    //执行头插操作
    prev->next = head;//连接第一个节点
    head = prev;//头插改变头指针的指向。
 
 
}

那么后面规律自然清晰可寻了，我们这里考虑结束的情况。

选择什么循环和循环条件是什么问题就迎刃而解了。

按照前面的逻辑

prev跟上next，即prev=next;

next指向原先链表尾结点的指针指向部分，即next=NULL;

连接节点，prev->next=head;

再调整头指针的指向，即head=prev;

最终结果出来了，这个时候的head和prev指向新链表（反转链表）的第一个节点。next指向空，可作为循环条件。

最终结果如图：

代码就可以写了


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = head;//prev指向head指向的节点，即第一个节点。
    struct ListNode* next = head;//next也指向第一个节点。
 
    next = prev->next;//先让next指向下一个节点。
    prev->next = NULL;//将结点指针指向的节点的指针域置空，意味着把节点取下来了。
 
    while (next)
    {   
        //取第二个及之后的节点
        prev = next;
        next = prev->next;
        prev->next = NULL;
        //头插
        prev->next = head;
        head = prev;
    }
    return head;
 
 
}

提交一下。

挫折才是算法题的常态，不急看看红字说什么。

原来是空链表的情况啊。也就是题目所给示例3的情况。

最前面直接加个if判断就行了，空链表直接让他返回空指针就
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/937367