旅行社网站模版河池公司做网站

当前位置： 首页 > news >正文

旅行社网站模版,河池公司做网站,老域名新网站推广,软件开发工具包英文文章目录 一、移除链表元素思路一思路二 二、合并两个有序链表思路#xff1a;优化#xff1a; 三、反转链表思路一思路二 四、链表的中间节点思路一思路二 五、综合应用之链表的回文结构思路一#xff1a;思路二#xff1a; 一、移除链表元素 题目链接#xff1a;https:… 文章目录 一、移除链表元素思路一思路二 二、合并两个有序链表思路优化 三、反转链表思路一思路二 四、链表的中间节点思路一思路二 五、综合应用之链表的回文结构思路一思路二 一、移除链表元素 题目链接https://leetcode.cn/problems/remove-linked-list-elements/ 我们先来看看题目描述和第一个示例    根据题目描述我们就可以大致明白题意就是将一个链表中的某个值的节点删除然后返回新链表的头结点然后题目要我们实现的函数给了我们头结点以及要删除的数据我们要把相应的节点删除 思路一 首先最简单的思路就是我们可以通过之前实现的链表的方法用上首先使用Find方法找到对应的值然后使用Erase方法删除直到Find方法返回空指针结束    由于这个方法思路比较好实现这里就不再赘述了可以自己尝试一下我们的关键是更优方法的思路二 思路二 这个题其实跟我们在刷顺序表题的时候遇见类似的只不过之前要删除的是数组中的元素这道题是删除链表节点不过本质上是相同的上次我们使用了双指针这次我们还是可以使用双指针顺序表刷题参考【初阶数据结构与算法】沉浸式刷题之顺序表练习(顺序表以及双指针两种方法)    具体思路也很像之前的那个题题目让返回新链表的头结点没有说必须是原链表的头结点所以我们可以新建一个链表如果遍历到原链表中节点的值不是题目给定的值也就是不是我们要删除的节点那么我们就把它尾插到新链表    我们要注意的是如果遇到了要插入的节点但是新链表的头为空我们就要让新链表的头和尾都指向这个节点其它情况就正常尾插    还有一个重要的地方就是当我们把链表移动完毕之后新链表的尾结点可能还指向原链表的节点我们要把它置为空题解如下 typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newhead, newtail;newhead newtail NULL;ListNode pcur head;while(pcur){if(pcur-val ! val){if(newhead NULL){newhead newtail pcur;}else{newtail-next pcur;newtail pcur;}}pcur pcur-next;}if(newtail)newtail-next NULL;return newhead; }二、合并两个有序链表 题目链接https://leetcode.cn/problems/merge-two-sorted-lists/ 我们先来看看题目的描述和第一个示例 题目给我们两个有序链表要求我们把这两个链表合并成一个新的有序链表然后返回它的头结点 思路 这个问题是不是有点似曾相识跟我们之前的合并有序数组是一样的我们当时的方法就是使用双指针只是合并有序数组时是要求我们在第一个数组中进行修改不能新建一个数组返回    但是这道题还要简单一些它可以新建一个链表我们可以通过双指针遍历要合并的链表比较两个链表中节点的大小谁小谁就尾插到新链表直到有一个链表走到空就停止循环    但是我们要注意的一点是虽然有一个链表走到空了也就是一个链表中的节点都插入到新链表了但是另一个链表可能还有节点所以我们要判断一下如果两个链表中还有一个链表不为空那么直接将它的所有节点尾插到新链表    还有就是做一个特殊处理因为两个链表中可能有空链表上面的方法就跑不通所以我们判断一下如果有一个链表为空那么直接返回另一个链表题解如下 typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 NULL){return list2;}if(list2 NULL){return list1;}ListNode* pcur1, pcur2;ListNode newhead, newtail;pcur1 list1;pcur2 list2;newhead newtail NULL;while(pcur1 pcur2){if(pcur1-val pcur2-val){if(newhead NULL){newhead newtail pcur1;}else{newtail-next pcur1;newtail pcur1;}pcur1 pcur1-next;}else{if(newhead NULL){newhead newtail pcur2;}else{newtail-next pcur2;newtail pcur2;}pcur2 pcur2-next;}}if(pcur1){newtail-next pcur1;}if(pcur2){newtail-next pcur2;}return newhead; }优化 上面的代码是一种题解但是我们可以发现这个代码写起来有点麻烦有一些重复的动作就是在每次插入之前我们要判断链表是否为空如果为空要让新链表的头和尾都指向要插入的节点    那我们能不能让代码更加简洁一点呢就是不必每次插入节点前都判断链表是否为空这里就可以用上我们之前学过的带头的概念我们申请一个不保存数据的哨兵位当作链表默认的头    这样我们的新链表默认就有了一个节点不为空了可以直接在哨兵位后面尾插节点不用判断链表是否为空最后返回时就返回哨兵位的下一个节点就可以了它就是我们新链表中保存数据的头节点    不过由于我们的哨兵位是通过malloc来的所以最后代码结束时不要记得把它释放掉以免造成内存泄漏如下 typedef struct ListNode ListNode; struct ListNode mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 NULL){return list2;}if(list2 NULL){return list1;}ListNode* pcur1, pcur2;pcur1 list1, pcur2 list2;ListNode newhead, newtail;newhead newtail (ListNode)malloc(sizeof(ListNode));while(pcur1 pcur2){if(pcur1- val pcur2-val){newtail-next pcur1;newtail pcur1;pcur1 pcur1-next;}else{newtail-next pcur2;newtail pcur2;pcur2 pcur2-next;}}if(pcur1){newtail-next pcur1;}if(pcur2){newtail-next pcur2;}ListNode* ret newhead-next;free(newhead);newhead NULL;return ret; }三、反转链表 题目链接https://leetcode.cn/problems/reverse-linked-list/ 我们来看看题目描述和第一个示例    题目要求我们将给出的链表反转就是改变指针的指向让原本的尾节点变成头让原本的头结点变成尾 思路一 思路一还是很简单就是我们创建一个新链表遍历原链表拿原链表中的节点头插到新链表就可以了如图    有了上图的分析实现就很简单了只需要一个头插方法我们之前讲过这里就不再赘述了可以自己试试我们重点介绍思路二 思路二 思路二比较难想出来但是确实非常快因为它是对原链表的节点的指针指向进行修改所以很快并且不会消耗什么空间思路如图    有了上面的思路我们就可以来写代码了但是我们要注意一个点就是如果题目直接给出一个空链表让我们反转那么我们对它解引用就会出错所以我们特殊处理一下如果链表为空就直接返回空链表反转还是空链表题解如下 typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) {if(head NULL){return head;}ListNode* n1, *n2, n3;n1 NULL;n2 head;n3 head-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3)n3 n3-next;}return n1; }四、链表的中间节点 题目链接https://leetcode.cn/problems/middle-of-the-linked-list/ 我们来看看题目描述和两个示例如下    它的要求就是让我们返回链表的中间节点如果是偶数个节点那么就有两个中间节点则返回后一个节点 思路一 我们首先能想到的思路就是先遍历整个链表看看链表一共有多少个节点然后让它除以2最后再次循环遍历链表就可以找到中间节点这个题很简单我们直接给出题解如下 typedef struct ListNode ListNode; struct ListNode middleNode(struct ListNode* head) {int count 0;ListNode* pcur head;while(pcur){count;pcur pcur-next;}count / 2;pcur head;while(count–){pcur pcur-next;}return pcur; }虽然这个方法看起来已经很简单了但是始终都是执行了两次循环有没有更简单的方法呢接下来我们来看看思路二 思路二 思路二的方法很绝妙简单又快捷就是使用快慢指针的算法快慢指针默认都指向头结点慢指针一次走一步快指针一次走两步那么等快指针走到空的时候慢指针指向的节点就是中间节点    为什么呢因为快指针每次走的距离都是慢指针的2倍最后统计一共走的距离时快指针走的总距离也是慢指针的2倍而快指针走到了空也就说明走到了链表尾那么此时慢指针就是它的一半刚好指向中间节点题解如下 typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) {ListNode* slow, fast;slow fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}return slow; }五、综合应用之链表的回文结构 题目链接https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa 我们先来看看题目描述和它的第一个示例    题目要求我们判断给出的链表是否是一个回文结构也就是是否前后对称这道题就可以用上我们之前做题写出的代码具体后面再说我们先解决一个事情    就是这个题目没有提供C语言的选项那我们就选择C来做C是兼容C语言的主要是我们要知道在哪里写代码如图 这是C中的类但是不影响我们做题我们只需要知道我们把代码写在哪里在题目中也有提示把代码写在紫色大括号内即可其它的可以不管还有一个就是C对结构体做了优化可以在使用结构体时不必加上struct 思路一 虽然判断链表是否是回文结构很难但是我们可以把链表中的数据存放到数组中判断数组是否是回文结构这个就比较简单了    由于链表两边的数据是对称的所以我们定义一个left和right分别指向数组的头和尾然后对比它们的值如果不同直接返回假否则的话就一直让它们往中间走直到left不再小于right    在循环过程中一旦left所在位置的值和right所在位置的值不相同就说明并不对称也就不是回文结构返回假一旦循环结束说明左右对称就是回文结构直接返回真    并且我们注意到虽然题目要求空间复杂度为O(1)但是同时又给出了链表的最大节点个数不超过900那定义一个901个元素大小的数组时间复杂度还是O(1)因为它始终还是常数个空间如下 class PalindromeList { public:bool chkPalindrome(ListNode A) {int arr[901] { 0 };ListNode* pcur A;int i 0;while(pcur){arr[i] pcur-val;pcur pcur-next;}int left 0, right i-1;while(left right){if(arr[left] ! arr[right]){return false;}left, right–;}return true;} };最后就是这个方法虽然很简单但是只适合给出了链表节点大小的题目如果遇到没有给出链表节点大小的题目就会导致时间复杂度变成O(N)导致不符合要求所以我们再介绍一个方法 思路二 这个思路可以帮我们复习上面做过的题让我们能够灵活运用知识具体思路就是我们首先通过找中间节点的函数找到链表中间节点然后从中间节点开始将后面的节点反转形成一个新链表然后再和原链表进行比较即可如图    找中间节点的函数和反转链表的函数可以从我们之前做过的题里面拿过来用当然也可以自己根据这个逻辑把中间的代码实现这里我就直接把之前写过的函数直接拿过来用如下 class PalindromeList {public:struct ListNode* reverseList(struct ListNode* head) {if (head NULL) {return head;}ListNode* n1, *n2, n3;n1 NULL;n2 head;n3 head-next;while (n2) {n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;}struct ListNode middleNode(struct ListNode* head) {ListNode* slow, fast;slow fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow;}bool chkPalindrome(ListNode A) {if(A NULL){return true;}ListNode* mid middleNode(A);ListNode* newlist reverseList(mid);ListNode* pcur1, *pcur2;pcur1 A, pcur2 newlist;while(pcur2){if(pcur1-val ! pcur2-val){return false;}pcur1 pcur1-next;pcur2 pcur2-next;}return true;} };那么今天的链表刷题训练就到这里结束啦有什么不懂欢迎提出我们下一篇文章还是刷题之后我们会讲栈和队列的实现敬请期待    bye~