leetcode链表刷题记录

news/2024/11/7 13:35:29/

题单:

 

 

一,移除链表元素

题目描述

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

题目接口:

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

题目解答:

做这道题需要分三种情况:

1.当链表为空链表时直接返回NULL便可。

2.当链表的头节点就是要删除的节点时就执行头删的逻辑,即:

当遇到这个用例时,需要删除的链表元素为7时便走第一个循环进行头删。不断调整head指针的指向。直到head指针指向NULL。

3.当要删除的节点不是头节点时,需要执行另一个删除元素的逻辑。这个逻辑需要用到三个指针:prev(要删除节点的前一个指针),cur(当前节点指针),next(要删除节点的下一个指针)。 

在定义时将prev初始化为NULL,cur初始化为head,next是cur指向的next(前提条件是cur不为NULL)。

即:

要删除的元素为2.

删除操作与不删除时的操作也是不一样的,删除时

1.prev不能动,动了就会与cur重叠。

2.next要在cur不为NULL时才能动。

不是删除操作时:

1.三个指针一起动

2.next要在cur不为NULL时才能动。

代码如下:

解题代码:

struct ListNode* removeElements(struct ListNode* head, int val){if(head == NULL)return NULL;//当头节点为要删除的值时struct ListNode* next = head->next;while(head&&head->val == val){free(head);head = next;if(head)next = head->next;}//当要删除的节点是另外的节点时struct ListNode* prev = NULL;struct ListNode* cur = head;while(cur){if(cur->val == val){free(cur);prev ->next = next;cur = next;if(cur)next = cur->next;}else{prev = cur;cur = next;if(cur)next = cur->next;}}
return head;
}

二,链表的中间节点

 题目描述:

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

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

题目接口:

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

题目解答:

要找到链表的中间节点,需要定义两个指针:1.快指针     2.慢指针

这两个指针在一开始时指向同一个节点,但在移动的过程中快指针的移动速度是慢指针的两倍。当快指针走到结尾时慢指针就走到了中间节点处。

 解题代码:

struct ListNode* middleNode(struct ListNode* head){//当链表为NULL时返回NULLif(head == NULL)return NULL;//当链表只有一个节点时返回这一个节点即可if(head->next == NULL)return head;//当链表内有多个节点时定义快慢指针,走快慢指针解法struct ListNode* fast = head;struct ListNode* slow = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

 三,查找链表的第k个节点

题目描述:

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

题目接口:

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

题目解答:

寻找链表的倒数第k个节点要分三种情况:

1.当链表为NULL时返回NULL

2.当k大于链表的长度时返回NULL

3.当前两种情况没有出现时就在fast比slow指针多走k步以后继续走直到fast指向NULL此时slow便指向倒数第k个节点,返回slow即可。

解题代码:

struct ListNode* getKthFromEnd(struct ListNode* head, int k){//当链表为NULL时if(head == NULL)return NULL;struct ListNode* fast = head;struct ListNode* slow = head;while(fast&&k){fast = fast->next;k--;}//当k的大小大于链表的长度时if(k>0)return NULL;//fast比slow的步长大k当fast指向NULL时,slow指向链表的倒数第k个节点while(fast){fast = fast->next;slow = slow->next;}return slow;
}

四,反转链表

题目描述:

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

题目接口:

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

题目解答:

反转链表这道题需要分三种情况来讨论:

1.链表为NULL时直接返回NULL即可。

2.链表只有一个节点时直接返回头节点即可

3.当链表内有多个节点时需要用到三个指针:prev,cur,next。通过这三个指针来对链表的指向进行反转,最后返回prev得到的便是反转后的指针。

解答代码:

struct ListNode* reverseList(struct ListNode* head){//当链表为NULL时直接返回NULLif(head==NULL){return NULL;}//当链表只有一个节点时if(head->next == NULL){return head;}//当链表内有多个节点时struct ListNode* prev = NULL;struct ListNode* cur = head;struct ListNode* next = head->next;while(cur){cur->next = prev;prev = cur;cur = next;if(cur)next = cur->next;}return prev;
}

五,链表的合并

题目描述:

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

题目接口:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){}

题目分析:

 要实现两个链表升序的合并需要讨论三种情况:

1.两个链表都是空链表时返回NULL

2.当两个链表中有一个链表为NULL时返回那个非空链表

3.当两个链表都不为NULL时要通过对比实现取小的尾插。在其中一个链表变成空链表时将另外一个非空的链表连接到新链表的后面便完成了链接两个链表的操作。

解题代码:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){//当两个链表都为NULL时直接返回NULLif(list1==NULL&&list2==NULL){return NULL;}//当两个链表中有一个为NULL一个不为NULL时返回不为NULL的if(list1==NULL){return list2;}if(list2==NULL){return list1;}//当两个链表都不为NULL时取小的尾插struct ListNode* newhead = NULL;struct ListNode* tail = NULL;while(list1&&list2){if(list1->val<list2->val){if(newhead == NULL){newhead = tail = list1;list1 = list1->next;}else{tail->next = list1;list1 = list1->next;tail = tail->next;}}else{if(newhead == NULL){newhead = tail = list2;list2 = list2->next;}else{tail->next = list2;list2 = list2->next;tail = tail->next;}}}if(list1)tail->next = list1;if(list2)tail->next = list2;return newhead;}

http://www.ppmy.cn/news/762554.html

相关文章

Stable Diffusion 使用 SadTalker 生成图片数字人

Heygen和D-ID等照片转视频的工具&#xff0c;都需要在线付费使用。本次介绍一个SadTalker数字人。SadTalker有多种使用方式&#xff0c;包括完整安装程序和stable diffusion插件模式。安装程序操作较繁琐&#xff0c;因此推荐stable diffusion插件模式。 文章目录 SadTalker安…

win10安装界面,键盘不能用解决办法

win10安装界面键盘不能用 用外接键盘&#xff0c;先按shiftf10, 弹出cmd,然后输入taskmgr.exe&#xff0c;然后按Enter键&#xff0c;就能打开任务管理器了&#xff0c;关掉一个IME为后缀的进程就可以了

键盘不能使用或者提示没有键盘开不了机的【解决办法】

没键盘开不了机&#xff1a; 一般情况下开机没有键盘是不行的&#xff0c;因为BIOS里一般会把开机检测设置为“ALL&#xff0c;But KeyBoard"就是说只有键盘有问题会提示错误&#xff0c;没有硬盘没有光驱没有网卡都没事&#xff0c;解决办法就是开机插上键盘或者将B…

修复系统时,鼠标键盘不能使用

进入系统修复选项鼠标键盘不能用怎么办 时间:2014-10-07 17:31 来源:学电脑吧整理 作者:秩名 有不少朋友可能在重装操作系统时遇到这样的情况&#xff0c;在我们进入系统修复选项时&#xff0c;发现不能鼠标和键盘选择相关菜单。是什么原因引起的呢&#xff0c;进入系统修复选…

键盘不能用了,usb无法识别键盘和鼠标,或者设备管理器中没有键盘或者鼠标,如何解决

情况&#xff1a; 台式电脑突然无法识别键盘&#xff0c;且我也不小心在设备管理器中将【键盘】这个设备卸载了。。此时&#xff0c;键盘无法使用&#xff0c;只有鼠标能用 解决方式&#xff1a; 首先点击设备管理器中最上面的菜单栏中【查看】&#xff0c;选择其中的【显示隐…

电脑键盘上方的功能键有时候不能用

Dell笔记本电脑Fn功能键可以这样设置&#xff1a; &#xff08;在百度上学到的&#xff0c;有兴趣可以看一下&#xff1a;https://jingyan.baidu.com/album/af9f5a2d45709e43140a45dc.html?picindex1&#xff09; 1/5 第一步&#xff1a;我们首先打开我们的Dell笔记本电脑&a…

键盘的win键不能用怎么办 电脑win键失效的原因及解决办法

电脑疑问 PConline IT百科 我们知道键盘的win键能快速打开开始菜单&#xff0c;配合其他键使用也能方便打开其他软件&#xff0c;可以让我们使用电脑更快捷&#xff0c;但是最近有的人发现自己电脑键盘的win键不能使用了&#xff0c;这是怎么回事呢?今天小编就来分享一下电脑…

安装VMware,主机键盘不能用解决方法

不是第一次出现这个问题了&#xff0c;记录一下 右键电脑-属性-硬件-设备管理器&#xff0c;键盘那一项显示黄色叹号&#xff0c;属性显示为 由于其配置信息&#xff08;注册表中的&#xff09;不完整或已损坏&#xff0c;Windows 无法启动这个硬件设备 VMware安装以后会在C盘…