【初阶数据结构与算法】链表刷题之移除链表元素、反转链表、找中间节点、合并有序链表、链表的回文结构

一、移除链表元素

题目链接：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~