【数据结构】链表题目解析＜leetcode&&牛客＞

用户10925563

发布于 2024-06-04 14:14:54

720

发布于 2024-06-04 14:14:54

文章被收录于专栏：c/c++&&linuxc/c++&&linux

1.leetcode

1.1 链表的中间结点

1.1.1 题目描述

题目链接：876. 链表的中间结点 - 力扣（LeetCode）

我们先看题目描述：

1.1.2 解题思路

我们用画图用快慢指针来解决这个问题

定义一个快指针fast，一个慢指针slow

快指针一次走两个结点，慢指针一次走一个结点

当快指针指向NULL或者快指针的下一个结点指向NULL的时候，慢指针刚好走到中间结点

有了这个思路，那我们就可以开始写代码了

1.1.3 代码实现

struct ListNode* middleNode(struct ListNode* head) 
{
    struct ListNode* fast=head,*slow=head;
    while( fast && fast->next )
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

1.2 移除链表元素

1.2.1 题目描述

题目链接：203. 移除链表元素 - 力扣（LeetCode）

1.2.2 解题思路

我们定义一个cur指向当前结点，定义prev指向前一个结点，next指向下一个结点

如果cur->val==val，那我们就删除这个结点

怎么删除呢：

我们让prev->next指向cur->next，然后free(cur)

为了防止野指针，我们可以定义一个next指向cur->next，先free(cur)，再让prev->next指向next

特殊情况

如果cur为第一个结点，那prev就是空，我们在这里得分成两种情况：

如果prev不为空，则prev->next=next；

如果prev为空，head=next；

由于链表是无序的，因此我们需要遍历一遍才能删除所有的val，可以使用while循环来控制

1.2.3 代码实现

根据解题思路，我们可以写代码了：

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    while(cur!=NULL)
    {
        if(cur->val==val)
        {
            struct ListNode* next=cur->next;
            free(cur);
            if(prev)
            {
                prev->next=next;
            }
            else
            {
                head=next;
            }  
            cur=next;   
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

1.3 反转链表

1.3.1 题目描述

题目链接：206. 反转链表 - 力扣（LeetCode）

1.3.2 分析题目

1.3.2.1 思路一

我们可以设计算法让整个链表掉头

定义三个代码n1,n2,n3

n1指向NULL，n2指向head，n3指向第二个结点

当n2不为NULL的时候，让n2->next反方向指向n1，然后n1，n2，n3都往后移动

当n3走到NULL的时候，会出现空指针的问题，这个时候我们给n3单独加一个判断

if(n3!=NULL)，n3=n3->next

注意：我们没有交换值，而是改变了指针的指向

另外，当链表本身为空的时候，直接返回NULL，所以我们也需要加一个判断链表为空的条件

1.3.2.2 思路二

定义一个newhead指向NULL作为新链表的头，定义cur指向原链表的第一个结点，next保存第二个结点

然后将cur尾插，newhead作为新的头，cur走到原链表的第二个结点，next指向next->next

最后，当cur不为空的时候，则进入循环，为了防止next成为空指针，我们加一个判断：

if(next!=NULL)，则next=next->next

同样的，当链表本身为空的时候，直接返回NULL，所以我们也需要加一个判断链表为空的条件

1.3.3 代码实现

1.3.3.1 代码一

根据思路一，我们可以写出下面的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    struct ListNode* n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    free(n3);
    free(n2);
    return n1;
}

1.3.3.2 代码二

根据思路二，我们可以写出下面的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    struct ListNode* next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        next=next->next;
    }
    free(next);
    free(cur);
    return newhead;
}

1.4 交叉链表

1.4.1 题目描述

题目链接：160. 相交链表 - 力扣（LeetCode）

1.4.2 题目分析

我们先要搞清楚一个概念，单链表可以相交，但绝对不会交叉

原因如下：

单链表中，多个结点可以存一个结点的地址，但是一个结点不可能存多个结点的地址

因为每个结点只有一个next

所以链表的相交一定是Y字形的

这里我们要做的有两步：

判断是否相交
找交点

1.4.2.1 思路一

暴力求解：A链表的所有结点依次去B链表找一遍

注意：一定要用结点的地址去比对

1.4.2.2 思路二

1.4.2.2.1 判断相交

分别找尾结点，尾结点地址相同就相交

1.4.2.2.2 找交点

算出两个链表的长度，得出两个链表的长度差，让长链表先走差距步，然后同时走，当第一个地址相同的时候，这就是交点

这个算法的时间复杂度是F(3N)，即O(N)

1.4.2.2.3 完整算法

我们先定义curA，curB分别指向两个链表，用while循环求长度，并判断是否相交（只有相交了才会有交点）如果不相交则返回NULL，相交再进行下一步

我们得到lenA和lenB，用C语言自带的函数abs求出差距的绝对值

int n=abs(lenA-lenB);

那么谁先走呢，我们用假设法：假设A长B短

如果假设错误，那就纠正过来

让长的先走差距步

然后同时走，想等的时候返回任意一个地址就是交点

1.4.3 代码实现

根据思路二，我们写出代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *curA=headA,* curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB=curB->next;
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int n=abs(lenA-lenB);
    struct ListNode *longList=headA, *shortList=headB;
    if(lenB>lenA)
    {
        longList=headB;
        shortList=headA;
    }
    while(n--)
    {
        longList=longList->next;
    }
    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }
    return longList;
}

1.5 环形链表

1.5.1 题目描述

题目链接：141. 环形链表 - 力扣（LeetCode）

1.5.2 题目分析

我们先了解一个知识：循环链表

尾结点不指向NULL，指向头就是循环链表

那么带环链表就意味着尾结点的next可以指向链表的任意一个结点，甚至可以指向他自己

这里我们的算法思路唯一靠谱的还是快慢指针

slow一次走一步，fast一次走两步，当slow走到中间的时候，fast一定入环了，如果fast指向NULL，则该链表无环

当slow再走一半也就入环了，这个时候，由于slow走的慢，fast走的快，所以fast和slow最终会相遇的

那我们的代码就应该是

如果fast或者fast->next为NULL则返回false

当fast或者fast->next不为NULL的时候，slow走一步，fast走两步，当fast==slow，则返回true

1.5.3 代码实现

根据思路我们就可以写代码了:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *fast=head,*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

1.6 环形链表的入环点

1.6.1 题目描述

题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

1.6.2 题目分析

我们假设起点到环的入口点的距离是L，入口点到相遇点的距离是X，环的长度是C

那么画图我们可以得知：

从开始到相遇时slow走的距离是L+X
从开始到相遇时fast走的距离是L+n*C+X

（n:slow进环前，fast已经在环里走了 n 圈）

由于fast=slow*2，所以我们可以得到结论：一个指针从相遇点开始走，一个指针从头开始走，最终会在入口点相遇

我们可以画图来证明一下：

1.6.3 代码示例

根据这个思路我们可以写出代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow,* fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)//相遇
        {
            struct ListNode *meet=slow;
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

1.7 合并两个有序链表

1.7.1 题目描述

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

1.7.2 题目分析

这个算法思路很简单：就是直接找小尾插

定义一个tail和head，对比两个链表结点的val，小的尾插到tail->next，如果一个链表先走完，就把另外一个链表尾插到tail->next，最后返回head就行

具体的流程就是：

有一个特殊情况就是：如果list1和list2有一个为空的话，那就直接返回另外一个链表

1.7.3 代码实现

有了思路，我们就可以写代码了：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;
    struct ListNode*tail=NULL,*head=NULL;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            if(tail==NULL)
                head=tail=list1;
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
         else
        {
            if(tail==NULL)
                head=tail=list2;
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    }
    if(list1)
    tail->next=list1;
    if(list2)
    tail->next=list2;
    return head;
}

1.8 随机链表的复制

1.8.1 题目描述

题目链接：138. 随机链表的复制 - 力扣（LeetCode）

1.8.2 题目分析

这个题目很长，但是意思其实很简单：就是一个单链表，每个结点多了一个指针random随机指向链表中的任意结点或者NULL，我们血需要复制这个链表，连同random一起复制下来

1.8.2.1 思路一

思路一是我们用cur遍历链表，用for循环找random对应的原链表中的random，这个算法找每个random的时间复杂度都是O(N)，整个算法的时间复杂度是O(N^2)

1.8.2.2 思路二

思路二是分三步走：

将copy结点链接到原结点的next
copy结点的random指向对应原结点random的next
把copy链表拆接下来尾插到新链表

这个思路更优，时间复杂度是O(N)

我们可以简单画图来演示一下这三步：

1.8.2.2.1 copy结点插入到原结点的next

定义cur遍历链表，用malloc开辟一个copy的空间，然后依次将cur->val赋给copy->val，接着将copy结点插入到cur和cur->next之间，cur走到copy-.>next

1.8.2.2.2 处理copy结点的random

让cur回到head，经过第一步之后我们知道copy就是cur->next，这里我们分为两种情况：

如果cur->random指向NULL，则copy->next也指向NULL
否则copy->random指向cur->random->next

然后cur走到cur->next->next

1.8.2.2.3 copy结点拆解下来进行尾插

最后一步就是尾插，定义newhead和tail先指向NULL，cur回到head，copy是cur->next，next保存copy->next 将cpoy尾插到tail，将cur->next接到next恢复原链表，最后返回newhead

1.8.3 代码实现

我们根据思路二来写代码：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
	//copy结点插入到原结点的后面
    struct Node*cur=head;
    while(cur)
    {
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        copy->next=cur->next;
        cur->next=copy;
        cur=cur->next->next;
    }
    //处理copy结点的random
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }
    //copy结点拆下来尾插
    cur=head;
    struct Node*newhead=NULL,*tail=NULL;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        if(tail==NULL)
        {
            newhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;
        cur=next;
    }
    return newhead;
}

2.牛客题目

2.1 带哨兵位的单链表之链表分割

2.1.1 带哨兵位的单链表

链表分为两种：带头结点的和不带头结点的

之前我们学习了不带哨兵位的单链表，并实现了相关代码

现在我们认识一下带哨兵位头结点的单链表：

plist指向带哨兵位的头结点

这个结点不存储有效数据

如果为空链表：

不带头：plist指向NULL
带头：plist指向head，一定不会指向NULL

带哨兵位的单链表也有他自己的优势，我们用一道题来证明一下：

链表分割_牛客题霸_牛客网 (nowcoder.com)

2.1.2 题目描述

2.1.3 题目分析

假设有下面这个链表，给定数字5

那么排序后就是这样，不改变原来的数据顺序

可以分割成两个链表，plist1和plist2，小于x的结点尾插到plist1，否则尾插到plist2

当链表的数据全部尾插结束后，将plist2头结点尾插到plist1，这个时候带哨兵位的头结点就非常有优势了

我们可以定义两个头结点head和head2，分别作为两个链表的哨兵位，再定义两个尾结点tail1和tail2方便两个链表的尾插，定义cur遍历链表，和x值做比较

2.1.4 代码实现

我们思路清晰了就可以写代码了：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* head1,* head2,* tail1,* tail2;
        head1=(struct ListNode*)malloc(sizeof(struct ListNode));
        head2=(struct ListNode*)malloc(sizeof(struct ListNode));
        tail1=head1;
        tail2=head2;
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                tail1->next=cur;
                tail1=tail1->next;
            }
            else
            {
                tail2->next=cur;
                tail2=tail2->next;
            }
            cur=cur->next;
        }
        tail1->next=head2->next;
        tail2->next=NULL;
        pHead=head1->next;
        free(head1);
        free(head2);
        return pHead;
    }
};

由于该题只能用c++，但是我们可以完全按照C语言的语法规则写内部，最后就可以通过了;

2.2 快慢指针之链表中倒数第k个结点

2.2.1 题目描述

题目链接：链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

2.2.2 题目分析

我们可以利用快慢指针来解决问题：

2.2.2.1 思路一

先让fast走k步，这时候fast和slow之间的距离就是k，然后让fast和slow同时同步往后走，当fast走到NULL的时候，slow就指向了倒数第k个结点了

while(k--)就是走k步

2.2.2.2 思路二

先让fast走k-1步，这时候fas->next和slow之间的距离就是k，然后让fast和slow同时同步往后走，当fast->next走到NULL的时候，slow就指向了倒数第k个结点了

while(--k)就是走k-1步，由于fast走到NULL就没有fast->next了，这里我们需要加一个判断：

fast或者fast->next为NULL就返回NULL

2.2.3 代码实现

2.2.3.1 代码一

根据思路一，我们可以写出代码一

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead, *slow = pListHead;
    while(k--)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

2.2.3.2 代码二

根据思路二，我们可以写出代码二

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead, *slow = pListHead;
    while(--k)
    {
        if(fast==NULL||fast->next==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast->next)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

2.3 链表的回文结构

2.3.1 题目描述

题目链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

2.3.2 题目分析

我们的思路是：

找到中间结点
逆置后半段
比对

我们可以简单画个图来表示一下：

‘

奇数和偶数都是可以的

2.3.2.1 找中间结点

我们可以用快慢指针来找中：leetcode：链表的中间结点-CSDN博客

写一个找中的函数middleNode：

然后写一个逆置的函数reverseList：

我们画图表示一下头插的过程：

最后我们进行一个对比

2.3.3 代码实现

有了这个思路，我们就可以编写代码了：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode*reverseList(ListNode*head)
    {
        struct ListNode*cur=head;
        struct ListNode*newhead=NULL;
        while(cur)
        {
            struct ListNode*next=cur->next;
            //头插
            cur->next=newhead;
            newhead=cur;
            cur=next;
        }
        return newhead;
    }
    struct ListNode*middleNode(ListNode*head)
    {
        struct ListNode*slow,*fast;
        slow=fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    bool chkPalindrome(ListNode* head) {
        // write code here
        struct ListNode*mid=middleNode(head);
        struct ListNode*rhead=reverseList(mid);
        while(head&&rhead)
        {
            if(head->val!=rhead->val)
            {
                return false;
            }
            head=head->next;
            rhead=rhead->next;
        }
        return true;

    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除

链表

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度