数据结构与算法——链表OJ题详解（1）

一、前言

前几天博主已经给大家介绍完了单链表的一系列功能及实现，经过这几天的沉淀相信大家已经完全消化了吧！为了趁热打铁，这次up通过分享一些有关链表的OJ题来帮大家巩固巩固，来帮助大家拿捏单链表。

二、OJ题分享

2.1移除链表元素——非val尾插法

力扣203 移除链表元素链接

画图展示：

解题思路：定义一个新的pcur指针从头遍历原链表，如果结点的值不等于val就把结点尾插入到新链表中，如果结点的值等于val就继续遍历下一个结点，直到为空跳出循环为止。
代码展示：

//移除链表元素
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newphead = NULL;ListNode* newptail = NULL;ListNode* pcur = head;while(pcur){if(pcur->val!=val){if(newphead == NULL){newphead = newptail = pcur;}else {newptail->next = pcur;newptail = newptail->next;}}pcur = pcur->next;}if(newptail)newptail->next = NULL;return newphead;
}

2.2反转链表

力扣206链接 反转链表

2.2.1头插法

画图展示：


解题思路1：原链表不为空：遍历原链表，从第一个结点开始，如果此结点不为空，则直接头插到新链表中，直到原链表最后一个结点为止；原链表为空：直接返回NULL。

//反转链表头插法
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {ListNode* newphead = NULL;ListNode* ret = NULL;ListNode* pcur = head;while (pcur ){ret = pcur->next;//先把原链表结点保存下来，防止下面插入后原链表指针断裂pcur->next = newphead;newphead = pcur;pcur = ret;}return newphead;//如果链表为空直接返回NULL即可
}

2.2.2三指针法

画图展示


解题思路2：
创建三个指针变量n1,n2,n3,若n2不为空，则让n2->next=n1,再让n1 = n2,n2 = n3,如果n3不为空，n3 = n3->next,一直循环直到n2为空为止。
代码展示：

//反转链表三指针法
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL){return NULL;}ListNode* n1 = NULL;ListNode* n2 = head;ListNode* n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}

2.3链表的中间结点——快慢指针法

力扣876链接 链表的中间结点

画图展示：


解题思路：创建快慢指针slow和fast，快指针每次走两步，慢指针每次走一步，当fast为空或者fast->next为空时，slow结点的位置就是链表中间结点的位置。
代码展示：

//链表的中间结点快慢指针法
typedef  struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

2.4合并两个有序链表

力扣21 合并两个有序链表链接

2.4.1空链表法

画图展示：


解题思路：如果两个原链表都为空：直接返回NULL；如果有一个原链表为空：则返回另外一个链表的头结点；如果两个链表都不为空：创建一个新链表，同时遍历两个原链表，比较结点值的大小，把值小的结点插入到新链表中，然后再比较下一个结点中值的大小，直到某一个链表遍历到空为止，最后将另外一个链表剩下的结点依次插入到新链表中即可，最后再返回新链表的头结点。
代码展示：

//创建空链表法
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL)//判断原链表是否存在为空的情况{return list2;}if (list2 == NULL){return list1;}ListNode* l1 = list1;ListNode* l2 = list2;ListNode* newhead;ListNode* newtail;ListNode* newnode = NULL;newhead = newtail = newnode;while (l1 && l2)//原链表都不为空{if (l1->val < l2->val){if (newhead == NULL){newhead = newtail = l1;}else{newtail->next = l1;newtail = newtail->next;}l1 = l1->next;}else{if (newhead == NULL){newhead = newtail = l2;}else{newtail->next = l2;newtail = newtail->next;}l2 = l2->next;}}//一个链表已经遍历完，剩下另外一个链表if (l1){newtail->next = l1;}if (l2){newtail->next = l2;}return newhead;
}

2.4.2非空链表法

不知道在看完上面的空链表法之后，宝子们是否注意到这个细节呢


因为我们创建的新链表是空链表，所以我们在尾插第一个结点的时候，我们都会判断新链表是否为空的情况。但是这就出现了一个问题——反复出现了冗余的代码。我们都知道这是一个不好的习惯。那又有没有什么办法来避免呢？办法肯定是有的，既然你创建空链表要判断，那我们不如创建一个非空链表。
画图展示：


解题思路：先创建一个结点从而创立非空链表。如果两个原链表都为空：直接返回NULL；如果有一个原链表为空：则返回另外一个链表的头结点；如果两个链表都不为空：同时遍历两个原链表，比较结点值的大小，把值小的结点插入到新链表中，然后再比较下一个结点中值的大小，直到某一个链表遍历到空为止，最后将另外一个链表剩下的结点依次插入到新链表中即可，最后用rethead把newhead->next结点保存下来，再把newhead结点释放掉，最后在返回rethead结点。

//创建非空链表法
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL){return list2;}if (list2 == NULL){return list1;}ListNode* l1 = list1;ListNode* l2 = list2;ListNode* newhead;ListNode* newtail;ListNode* newnode = NULL;newnode = (ListNode*)malloc(sizeof(ListNode));newhead = newtail = newnode;while (l1 && l2){if (l1->val < l2->val){newtail->next = l1;newtail = newtail->next;l1 = l1->next;}else{newtail->next = l2;newtail = newtail->next;l2 = l2->next;}}if (l1){newtail->next = l1;}if (l2){newtail->next = l2;}ListNode* rethead = newhead->next;free(newhead);newhead = NULL;return rethead;
}

2.5链表的回文结构

牛客 链表的回文结构链接

2.5.1投机取巧数组法

画图展示：


解题思路：把链表中的元素放入数组中，创建left和right两个变量，分别是数组第一个元素下标和最后一个元素下标，当left<right时，判断arr[left]与arr[right]是否相等。相等则left++,right–。如果出现不相等的情况，则不是回文结构。如果当不满足left<right跳出循环的时候，依旧没有出现不相等的情况，则是回文结构。

//创建数组法
bool chkPalindrome(ListNode* A) {int arr[900] = {0};ListNode* pcur = A;int i = 0;while(pcur){arr[i++] = pcur->val;pcur = pcur->next;}int left = 0;int right = i-1;while(left<right){if(arr[left] != arr[right]){return false;;}left++;right--;}return true;}

2.5.2反转链表法

画图展示：

解题思路：先用快慢指针找到中间结点，再把中间结点及以后的结点反转，依次与前面的结点比较，判断值是否相等。

//反转链表法
ListNode* middleNode(ListNode* head) {//快慢指针找中间结点ListNode* slow;ListNode* fast;slow = fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;
}
ListNode* reverseList(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;
}bool chkPalindrome(ListNode* A) {ListNode* mid = middleNode(A);ListNode* right = reverseList(mid);ListNode* left = A;while (right) {if (left->val != right->val) {return false;}left = left->next;right = right->next;}return true;}

三、总结

OK啊，up这次就先给大家分享5道有关单链表OJ题。希望大家可以及时消化。但是up要分享的题还远远没有结束。剩下的OJ题我也会在整理完毕之后和大家分享。接着这些题目确实是有一些难度的，希望大家好好理解，认真消化，如果up描述的有拗口的地方还希望大家多多包含。最后就是解决这些题目的方法肯定是不止这一两种，up呢只是从复杂度优化的方面着手，如果大家有其他的好的方法欢迎大家@我。谢谢大家，请大家期待下一期OJ分享吧！记得一键三连哦。

学习如磨砺宝剑，日久见锋芒，愿你持之以恒，铸就辉煌人生。