【数据结构】链表相关题目（简单版）

2023-03-25

null next fast

🚀writeinfront🚀📜所属专栏：初阶数据结构🛰️博客主页：睿睿的博客主页🛰️代码仓库：🎉VS2022_C语言仓库🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！关注我，关注我，关注我，你们将会看到更多的优质内容！！文章目录前言习题1：习题2习题3衍生题1：衍生题2：习

🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

文章目录

前言
- 习题1：
- 习题2
- 习题3
- - 衍生题1：
  - 衍生题2：
- 习题4：
- 习题5：
总结

前言

在学完了顺序表的基本知识后，我们可以通过一些习题来巩固所学知识！

习题1：

删除链表中等于给定值 val 的所有结点。oj链接

这道题目有两种做法：

方法一：双指针的遍历，通过双指针来查找删除节点并连接后面的节点，但是缺点就是会有特殊情况需要考虑（头删的情况），代码如下：
方法2：通过遍历，将节点尾插到新链表，最后返回新链表，代码如下：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*cur=head,*newnode=NULL,*tail=NULL;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(newnode==NULL)
            {
                newnode=cur;
                tail=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;
            }
          cur=cur->next;
        }
        else
        {
            struct ListNode*next=cur;
            cur=next->next;
            free(next);
        }
    }
if(tail)
{
    tail->next=NULL;
}
  return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

习题2

反转一个单链表。oj链接

这道题也有两种方法，

方法1：用三指针的方法，前两个来改变每个节点的链接关系，最后一个节点用来标记位置方便遍历链表

代码如下：
方法2：取每个节点头插到新链表：

习题3

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。oj链接

这里我们就要介绍一下快慢指针了。通过快慢指针我们可以解决很多问题，以后都会用到。
那么什么是快慢指针呢？
顾名思义，快慢指针就是通过两个不同指针步长的不同来遍历链表。

这道题我们让一个指针走两步，一个指针走一步，当快指针指向空或快指针的next指向空的时候，慢指针指向位置就是中间节点位置。

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode*slow=head,*fast=head;

    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11

衍生题1：

输入一个链表，输出该链表中倒数第k个结点。oj链接

其实也是快慢指针的思想，只是这里不是步长的不同，而是起点不同：
要寻找倒数第k个节点，就让快指针的起点在慢指针的后k步。当快指针指向空的时候，慢指针就指向倒数第k个节点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* slow=pListHead;
    struct ListNode* fast=pListHead;
   
    while(k--)
    {
       
         if(fast==NULL)
    {
        return NULL;
    }
     fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

衍生题2：

给定一个链表，判断链表中是否有环。oj链接

这道题也是用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。~~比如：陪女朋友到操作跑步减肥。~~

那么，为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
代码如下：

bool hasCycle(struct ListNode *head) 
{
    struct ListNode*fast=head,*slow=head;
    if(head==NULL||head->next==NULL)
    {
        return false;
    }
    fast=fast->next;
    while(fast!=slow)
    {
        if(fast==NULL||fast->next==NULL)
            break;
        fast=fast->next->next;
        slow=slow->next;
    }
    if(fast==slow)
    return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

习题4：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的oj链表

这道题引入了哨兵位，也就是空的头节点。其实，对于链表尾插的时候，需要判断是否为空，比较麻烦，只要我们创建一个空的头节点就可以避免很多情况。

链表在头插的时候我们不需要头节点；
链表在尾插的有空的头节点会更方便。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*tail=newnode;
    tail->next=NULL;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            tail->next=list1;
            tail=list1;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=list2;
            list2=list2->next;
        }
    }

if(list1)
    tail->next=list1;
if(list2)
    tail->next=list2;

    return newnode->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

习题5：

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。oj链接

这道题我们创建两个新链表（带有哨兵位的空头节点），小于的尾插到一个链表，大于的尾插到另外一个链表，最后将他们连起来即可。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        // write code here
        struct ListNode*greaternode=NULL;
        struct ListNode*lessnode=NULL,*cur=pHead;
       
        struct ListNode* gtail=greaternode,*ltail=lessnode;
        while(cur!=NULL)
        {
            if(cur->val>=x)
            {
                gtail->next=cur;
                gtail=cur;
                cur=cur->next;
                gtail->next=NULL;
            }
            else
            {
                ltail->next=cur;
                ltail=cur;
                cur=cur->next;
                ltail->next=NULL;
            }
        }
        ltail->next=greaternode->next;
        return lessnode->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30