(C语言版)力扣(LeetCode)+牛客网(nowcoder)链表相关面试题OJ题解析(下)

简介: 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

CM11 链表分割


题目


现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

题目链接:链表分割


解法


代码如下:


class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* moretail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* less=lesstail;
        struct ListNode* more=moretail;
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                less->next=cur;
                less=less->next;
                cur=cur->next;
            }
            else 
            {
                more->next=cur;
                more=more->next;
                cur=cur->next;
            }
        }
        more->next=NULL;
        less->next=moretail->next;
        pHead=lesstail->next;
        free(lesstail);
        free(moretail);
        return pHead;
    }
};


这里的题,没有c语言选项,可以直接在c++里写也是没有问题的,因为c++兼容c的大部分代码,首先我们创建两个临时空间用于保存较小值和较大值的链表空间分别复制给less和more两个指针,将pHead复制给cur指针,然后利用循环将cur指针逐个遍历pHead中的结点值与val进行比较,较小值用less指向,较大值用more指向,最后more再指向NULL(此时more指向的应该是最后的结点),less指向moretail第一个结点,再将pHead指向lesstail第一个结点,再将两个临时空间释放,最后返回pHead即为分割好的链表。


OR36 链表的回文结构


题目


对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。


测试样例:1->2->2->1

返回:true

题目链接:链表的回文结构


解法


代码如下:


class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        struct ListNode*slow=A;
        struct ListNode*fast=A;
        while(fast->next)
        {
            slow=slow->next;
            fast=fast->next;
        }
        struct ListNode*change=NULL;
        struct ListNode*head=slow;
        while(head)
        {
            struct ListNode*next=slow->next;
            head->next=change;
            change=head;//重新置头
            head=next;
        }
        while(slow)
        {
            if(A->val!=change->val)
            {
                return false;
            }
            slow=slow->next;
            change=change->next;
        }
        return true;
    }
};


这个算法的思路是先建立两个快慢指针,fast指针走两步,slow指针走一步,当fast指针遍历完整个链表时,slow指向链表中间位置,再创建两个指针一个指向NULL,另一个复制slow当前地址,再将slow之后的链表进行反转,再比较,只要有一个值不相等即返回false,遍历后都相等,返回ture。


160. 相交链表


题目


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


图示两个链表在节点 c1 开始相交:


e7a55ad20776487d9db51d6b03609aa7.png


题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构。

题目链接:相交链表


解法


代码如下:


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
        struct ListNode *p, *q;
        for (p = headA, q = headB; p != q; ){
            if (p != NULL)
                p = p->next;
            else 
                p = headB;
            if (q != NULL)
                q = q->next;
            else 
                q = headA;
        }
        return p;
}


这种算法的主体思路为复制AB两个头结点指针,两个结点同时开始遍历,如果第一趟遍历不相等,那先到尾结点的指针先走到另一头结点的位置,之后另一个指针接着走一步,如果两指针不相等,就一直进入循环,直至两指针相等跳出循环,最后返回其中一个结点即为相交结点。

上述代码可改为下面的简洁形式:


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL)
        return NULL;
    struct ListNode *p=headA,*q=headB;
    while(p!=q)
    {
        p=p==NULL?headB:p->next;
        q=q==NULL?headA:q->next;
    }
    return q;
}


141. 环形链表


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

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

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

题目链接:环形链表


解法


代码如下:


bool hasCycle(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}


这里使用快慢指针的写法,slow指针从头开始,fast指针从第二个结点开始,首先在循环中,如果fast指针走到了NULL或下一结点为空,则直接返回false,如果是环状的,则fast指针走两步,slow指针走一步,最终两指针会相遇, 最后跳出循环,返回ture。


142. 环形链表 II


题目


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

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

不允许修改 链表。

题目链接:环形链表||


解析


代码如下:


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


这种解法思路延续上一题的快慢指针,只不过fast指针也是从头开始以及返回值改变了,遍历环形链表fast等于slow时,此时先判断slow是否等于头结点,如果等于头结点,则直接返回头结点,如果不等,则进入循环,各自走一步,直至相等,返回相等时的结点即为环结点。


138. 复制带随机指针的链表


题目


给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。


构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。


例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。


返回复制链表的头节点。


用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:


val:一个表示 Node.val 的整数。

random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

题目链接:复制带随机指针的链表


解析


代码如下:


struct Node* copyRandomList(struct Node* head) {
    if(head == NULL)
        return NULL;
    struct Node* p = head;
    struct Node* phead = (struct Node*)malloc(sizeof(struct Node));//复制后要返回的链表头结点
    struct Node* ph = phead;//复制phead结点
    while(p)//p不为NULL则一直循环
    {
        struct Node* tmp = p->next;//保存p的下一结点
        ph->val = p->val;//复制值到pHead
        p->next = ph;//p指向ph
        ph->random = p->random;//复制random指针给ph
        ph->next = (struct Node*)malloc(sizeof(struct Node));//开辟下一结点空间
        if(tmp)
            ph = ph->next;//为真表示后面还有结点,ph指向下一结点
        else
            ph->next = NULL;//为假表示后面没结点了
        p = tmp;//p指向p的下一结点
    }
    ph = phead;//再复制phead到ph
    while(ph)
    {
        if(ph->random)//random指向空则不执行
            ph->random = ph->random->next;//random指向的修正
        ph = ph->next;//指向下一结点
    }
    return phead;
}


代码分析我写在注释中了,主要思路是,先将p(head)的val复制到ph(phead),然后将p的next指向当前ph结点,然后将p当前的random复制给ph(phead)的random,遍历直至p指向空,再将ph(phead)的random指向修正,最后phead即为复制后的链表

可以结合作者画的草图理解一下:


e8f7620a40844d66932921073348c7eb.png


这个图可能画的不好,小伙伴如果理解不了可以自己画一遍推一下代码,应该就可以理解了。


结语


这里的解法代码部分来自力扣官方和作者自己的解法,作者只是进行了详细的剖析和部分改动方便大家理解和提升自己,学会多角度观察问题,解决问题。


有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!

制作不易,如有不正之处敬请指出

感谢大家的来访,UU们的观看是我坚持下去的动力

在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!

f02ef3377a39412f994af9860ac232fc.png

相关文章
|
9天前
|
存储 NoSQL Java
【面试宝藏】Redis 常见面试题解析
Redis 是内存数据结构存储系统,用作数据库、缓存和消息中间件,支持字符串、哈希、列表等数据类型。它的优点包括高性能、原子操作、持久化和复制。相比 Memcached,Redis 提供数据持久化、丰富数据结构和发布/订阅功能。Redis 采用单线程模型,但通过 I/O 多路复用处理高并发。常见的面试问题涉及持久化机制、过期键删除、回收策略、集群和客户端等。
38 4
|
9天前
|
存储 关系型数据库 MySQL
【面试宝藏】MySQL 面试题解析
MySQL面试题解析涵盖数据库范式、权限系统、Binlog格式、存储引擎对比、索引原理及优缺点、锁类型、事务隔离级别等。重点讨论了InnoDB与MyISAM的区别,如事务支持、外键和锁机制。此外,还提到了Unix时间戳与MySQL日期时间的转换,以及创建索引的策略。
24 4
|
1天前
链表OJ题
链表OJ题
22 8
|
9天前
|
存储 缓存 NoSQL
【面试宝藏】Redis 常见面试题解析其二
Redis 高级面试题涵盖了哈希槽机制、集群的主从复制、数据丢失可能性、复制机制、最大节点数、数据库选择、连通性测试、事务操作、过期时间和内存优化等。Redis 使用哈希槽实现数据分布,主从复制保障高可用,异步复制可能导致写操作丢失。集群最大支持1000个节点,仅允许单数据库。可通过 `ping` 命令测试连接,使用 `EXPIRE` 设置过期时间,`MULTI/EXEC` 等进行事务处理。内存优化包括合理数据类型、设置过期时间及淘汰策略。Redis 可用作缓存、会话存储、排行榜等场景,使用 `SCAN` 查找特定前缀键,列表实现异步队列,分布式锁则通过 `SET` 命令和 Lua 脚本实现。
24 5
|
7天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
11天前
|
SQL 算法 大数据
深入解析力扣184题:部门工资最高的员工(子查询与窗口函数详解)
深入解析力扣184题:部门工资最高的员工(子查询与窗口函数详解)
|
11天前
|
SQL 算法 数据挖掘
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
|
11天前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
1天前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
9天前
|
安全 Java 数据安全/隐私保护
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
16 0