C/C++数据结构之链表题目答案与解析

avatar
作者
筋斗云
阅读量:0

个人主页点我进入主页

专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶

欢迎大家点赞,评论,收藏。

一起努力,一起奔赴大厂。

目录

1.前言 

2.题目解析

2.1 移除链表元素

2.2反转链表

2.3链表的中间结点

2.4链表中倒数第k个结点

2.5合并两个有序链表

2.6链表分割

3.结语


1.前言 

        在前面我们讲解了一些关于链表的内容,其中还有一些关于链表的习题,今天我们主要对这些题目进行解析。

2.题目解析

2.1 移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 

示例 2:

输入:head = [], val = 1 输出:[] 

示例 3:

输入:head = [7,7,7,7], val = 7 输出:[] 

提示:

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50
struct ListNode* removeElements(struct ListNode* head, int val) {     struct ListNode *phead=(struct ListNode*)malloc(sizeof(struct ListNode));     phead->next=head;     struct ListNode *p=phead;     struct ListNode *q=phead->next;     if(!q)         return NULL;     while(q)     {         if(q->val==val)         {             p->next=q->next;             free(q);             q=p->next;         }         else          {             p=p->next;             q=q->next;         }     }     return phead->next; }

        在这里我们需要对链表看是不是空的,只有一个节点,有多个节点这些情况进行讨论,我们建立一个带头节点的节点,然后将这些连上,先判断是不是空,不是空两个指针,一个指向建立的头节点,另一个指向后一个节点,我们针对后面的节点进行判断,值相等进行去除 操作,最后返回头节点的下一个节点。

2.2反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 

示例 2:

输入:head = [1,2] 输出:[2,1] 

示例 3:

输入:head = [] 输出:[] 

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

struct ListNode* reverseList(struct ListNode* head) {     struct ListNode *phead=(struct ListNode *)malloc(sizeof(struct ListNode));     struct ListNode *p=head;     phead->next=NULL;     if(!p)         return NULL;     struct ListNode *q=p->next;     while(p)     {         p->next=phead->next;         phead->next=p;         p=q;         if(q)             q=q->next;     }     return phead->next; }

        我们建立一个头节点,然后连起来,判断是不是为空,我们知道头插相当于将数据进行反转,所以我们可以将链表一次一次地拆下来,然后头插到头节点上,我们用两个指针,一个用来记录位置,一个用来进行拆地操作。

2.3链表的中间结点

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:head = [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为 3 。 

示例 2:

输入:head = [1,2,3,4,5,6] 输出:[4,5,6] 解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。 

提示:

  • 链表的结点数范围是 [1, 100]
  • 1 <= Node.val <= 100
struct ListNode* middleNode(struct ListNode* head) {     struct ListNode*fast=head,*slow=head;     if(!fast)         return NULL;     while(fast&&fast->next)     {         fast=(fast->next)->next;         slow=slow->next;     }     return slow; }

        我们先对链表进行判断是不是空链表,然后利用快慢指针进行操作,快指针每次走两步,满指针每次走一步,当快指针为空且快指针地下一个指针不为空就进行,知道出现这两个有一个为空才停止。

2.4链表中倒数第k个结点

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

示例1

输入:

1,{1,2,3,4,5}

复制返回值:

{5}
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {     // write code here     struct ListNode * flast=pListHead;     while(k--)     {         if(flast==NULL)             return NULL;         flast=flast->next;     }     struct ListNode *slow=pListHead;     while(flast)     {         slow=slow->next;         flast=flast->next;     }     return slow; }

        在这里我们同样用快慢指针,我们先让快指针走k步如果在k次中出现为空说明超出限制,返回空,快指针走k步后快慢指针一起走当快指针指向空此时地慢指针就是倒数第k个节点。

2.5合并两个有序链表

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

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 

示例 2:

输入:l1 = [], l2 = [] 输出:[] 

示例 3:

输入:l1 = [], l2 = [0] 输出:[0] 

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {     struct ListNode*phead=(struct ListNode *)malloc(sizeof(struct ListNode));     struct ListNode*s1=list1,*s2=list2,*cur=phead;     while(s1&&s2)     {         if(s1->val<=s2->val)         {             cur->next=s1;             cur=cur->next;             s1=s1->next;             cur->next=NULL;         }         else         {             cur->next=s2;             cur=cur->next;             s2=s2->next;             cur->next=NULL;         }     }     if(!s1)     {         cur->next=s2;     }     else{         cur->next=s1;     }     return phead->next; }

        在这里我们创建一个头节点,然后两个指针指向这两个链表,当这两个指针有一个为空时结束循环,循环里就是找到这两个指针地数据哪一个小,去连上头节点进行尾插,这两有一个为空时另外一个直接连上。

2.6链表分割

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

class Partition { public:     ListNode* partition(ListNode* pHead, int x) {         // write code here                 ListNode *list1=(ListNode*)malloc(sizeof(ListNode));         ListNode *list2=(ListNode*)malloc(sizeof(ListNode));         ListNode*s1=list1,*s2=list2;         list1->next=NULL;         list2->next=NULL;         ListNode*p=pHead;         while(p)         {             if(p->val<x)             {                 s1->next=p;                 p=p->next;                 s1->next=NULL;             }             else              {                 s2->next=p;                 p=p->next;                 s2->next=NULL;             }         }         s1->next=list2->next;         free(list2);     return list1->next;  }

        我们创建两个头节点,然后将小于x的放在一个链表上,大于等于X的放在另一个链表,最后连起来。

3.结语

        数据结构的学习非常的重要,我们想要学习好数据结构需要我们多多的刷题,希望大家可以在平时多多刷题来提升自己,最后希望大家可以三连一下

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!