【初阶数据结构与算法】链表刷题之移除链表元素、反转链表、找中间节点、合并有序链表、链表的回文结构
文章目录
一、移除链表元素
题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
我们先来看看题目描述和第一个示例：
根据题目描述我们就可以大致明白题意，就是将一个链表中的某个值的节点删除，然后返回新链表的头结点，然后题目要我们实现的函数给了我们头结点，以及要删除的数据，我们要把相应的节点删除
思路一
首先最简单的思路就是，我们可以通过之前实现的链表的方法用上，首先使用Find方法找到对应的值，然后使用Erase方法删除，直到Find方法返回空指针结束
由于这个方法思路比较好实现，这里就不再赘述了，可以自己尝试一下，我们的关键是更优方法的思路二
思路二
这个题其实跟我们在刷顺序表题的时候遇见类似的，只不过之前要删除的是数组中的元素，这道题是删除链表节点，不过本质上是相同的，上次我们使用了双指针，这次我们还是可以使用双指针，顺序表刷题参考：【初阶数据结构与算法】沉浸式刷题之顺序表练习(顺序表以及双指针两种方法)
具体思路也很像之前的那个题，题目让返回新链表的头结点，没有说必须是原链表的头结点，所以我们可以新建一个链表，如果遍历到原链表中节点的值不是题目给定的值，也就是不是我们要删除的节点，那么我们就把它尾插到新链表
我们要注意的是，如果遇到了要插入的节点，但是新链表的头为空，我们就要让新链表的头和尾都指向这个节点，其它情况就正常尾插
还有一个重要的地方就是，当我们把链表移动完毕之后，新链表的尾结点可能还指向原链表的节点，我们要把它置为空，题解如下：
typedefstructListNode ListNode;structListNode*removeElements(structListNode* 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/
我们先来看看题目的描述和第一个示例：
题目给我们两个有序链表，要求我们把这两个链表合并成一个新的有序链表，然后返回它的头结点
思路：
这个问题是不是有点似曾相识，跟我们之前的合并有序数组是一样的，我们当时的方法就是使用双指针，只是合并有序数组时是要求我们在第一个数组中进行修改，不能新建一个数组返回
但是这道题还要简单一些，它可以新建一个链表，我们可以通过双指针遍历要合并的链表，比较两个链表中节点的大小，谁小谁就尾插到新链表，直到有一个链表走到空就停止循环
但是我们要注意的一点是，虽然有一个链表走到空了，也就是一个链表中的节点都插入到新链表了，但是另一个链表可能还有节点，所以我们要判断一下，如果两个链表中还有一个链表不为空，那么直接将它的所有节点尾插到新链表
还有就是做一个特殊处理，因为两个链表中可能有空链表，上面的方法就跑不通，所以我们判断一下，如果有一个链表为空，那么直接返回另一个链表，题解如下：
typedefstructListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* 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){ 
