文章目录
一、前言
前几天博主已经给大家介绍完了单链表的一系列功能及实现，经过这几天的沉淀相信大家已经完全消化了吧！为了趁热打铁，这次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反转链表
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链表的中间结点——快慢指针法
画图展示：
解题思路：创建快慢指针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合并两个有序链表
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分享吧！记得一键三连哦。
学习如磨砺宝剑，日久见锋芒，愿你持之以恒，铸就辉煌人生。
