❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向：C/C++方向
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述，我们进入今天的力扣题目介绍——
目录
正文
一、合并两个有序链表问题
博主题解链接：创建新链表、尾插解决合并两个有序链表问题
推荐大家可以直接去看博主在力扣上面写的题解，介绍的还是比较详细的。
题目描述：
1、思路
我们的思路是：创建新链表，遍历并且比较原链表中节点的值，小的尾插到新链表中。
2、解题过程
像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。
如下图所示——
接下来我们实现一下这个程序——
第一次尝试写出的代码演示：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1 == NULL)
{
return list2;
}
if(list2 == NULL)
{
return list1;
}
// //创建空链表
// ListNode* newHead, *newTail;
// newHead = newTail = NULL;
//创建非空链表
ListNode* newHead, *newTail;
newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
//遍历原链表
ListNode* l1 = list1;
ListNode* l2 = list2;
while(l1 != NULL && l2 != NULL)
{
if(l1->val < l2->val)
{
//l1尾插
if(newHead == NULL)
{
//空链表
newHead = newTail = l1;
}
else
{
//非空链表
newTail->next = l1;
newTail = newTail->next;
}
l1 = l1->next;
}
else
{
//l2尾插
if(newHead == NULL)
{
//空链表
newHead = newTail = l2;
}
else
{
//非空链表
newTail->next = l2;
newTail = newTail->next;
}
l2 = l2->next;
}
}
//l1为空 l2为空
//l1和l2同时为空（不可能，有前后关系，肯定一个先一个后）——除非你给的两个都是空链表
if(l1)
{
newTail->next = l1;
}
if(l2)
{
newTail->next = l2;
}
return newHead;
}复杂度：时间复杂度：O(N)，空间复杂度：O(1)。
这里其实造成代码冗余了，根本原因在于——
链表存在为空的情况——需要特殊处理一下（下面会介绍具体怎么特殊处理）
3、改进方案
前文博主说明了，这几篇有关单链表应用的博客只要是LeetCode上面的题目，博主都在力扣上面发布了题解，而且博主都在画图软件上面把全部的逻辑实现了一遍，所以直接展示截图。
如下图所示——
既然问题出在链表存在为空的情况上，那我们直接创建非空链表不就行了吗？——
我们直接创建非空链表，用哨兵位充当头节点——
我们这里引入了“哨兵位”这个概念，今后我们要有这个意识。
这里我们真正要返回的是newHead的下一个节点，我们取名为retHead，而这里的newHead就是所谓的“哨兵位”，我们最后会删掉，返回etHead。
代码演示：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1 == NULL)
{
return list2;
}
if(list2 == NULL)
{
return list1;
}
//创建非空链表
ListNode* newHead, *newTail;
newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
//遍历原链表
ListNode* l1 = list1;
ListNode* l2 = list2;
while(l1 != NULL && l2 != NULL)
{
if(l1->val < l2->val)
{
//l1尾插
newTail->next = l1;
newTail = newTail->next;
l1 = l1->next;
}
else
{
//l2尾插
newTail->next = l2;
newTail = newTail->next;
l2 = l2->next;
}
}
//l1为空 l2为空
//l1和l2同时为空（不可能，有前后关系，肯定一个先一个后）——除非你给的两个都是空链表
if(l1)
{
newTail->next = l1;
}
if(l2)
{
newTail->next = l2;
}
ListNode* retHead = newHead->next;
free(newHead);
newHead = NULL;
return retHead;
}复杂度：时间复杂度：O(N)，空间复杂度：O(1)。
4、不建议使用的方案
那有朋友又要提出想法了——这样不也挺冗余的吗？干脆省略前面的判断l1、l2表空不也可以吗？
——博主这里不建议uu们这么做。
为什么不建议呢？
需要把newHead->next（newHead的下一个节点）手动置为空，还有可能要补充其他的，并没有达到简化的目的，只是看上去简化了代码，复杂度没区别。
代码演示：
//省略前面的判断l1、l2表空
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//创建非空链表
ListNode* newHead, *newTail;
newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
newHead->next = NULL;
//遍历原链表
ListNode* l1 = list1;
ListNode* l2 = list2;
while(l1 != NULL && l2 != NULL)
{
if(l1->val < l2->val)
{
//l1尾插
newTail->next = l1;
newTail = newTail->next;
l1 = l1->next;
}
else
{
//l2尾插
newTail->next = l2;
newTail = newTail->next;
l2 = l2->next;
}
}
//l1为空 l2为空
//l1和l2同时为空（不可能，有前后关系，肯定一个先一个后）——除非你给的两个都是空链表
if(l1)
{
newTail->next = l1;
}
if(l2)
{
newTail->next = l2;
}
ListNode* retHead = newHead->next;
free(newHead);
newHead = NULL;
return retHead;
}
//不建议删掉，这里删了，别的地方要加东西了复杂度：时间复杂度：O(N)，空间复杂度：O(1)。
再强调一遍，如果省略前面的判断l1、l2表空，这里不建议删，这里删了，别的地方要加东西了。
二、链表的回文结构问题
这道题是牛客网上面的题目，因为也是链表专题的，博主就一并放到LeetCode专栏了。
牛客网链接：OR36 链表的回文结构
因为是牛客网的题，博主还没有在牛客网写过题解，所以不放题解链接了，这题博主会细讲。
题目描述：
什么是“回文” ？比方说这些——
1、思路
我们先想想可以怎么做。
我们的思路是：创建新链表，保存原链表中的所有节点，反转新链表，比较新旧链表中所有节点的值是否相同——
这里我们就注意如图所示的这个就可以了。
这个思路我们就不实现了。 这是思路1。
思路2：我们创建大小为900的数组，遍历链表将节点的值依次存储在数组中，若数组为回文结构，则链表就是回文结构。
2、解题过程——投机取巧法
这个思路写的其实是投机取巧的办法，牛客网判题没有像力扣那么严格，所以能过，如果是在力扣上面，这个写法的时间复杂度肯定过不了了。
我们根据思路2来实现一下代码——
代码演示：
//投机取巧法
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
int arr[900] = { 0 };
// write code here
//遍历链表，将链表中节点的值依次存储到数组中
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)，空间复杂度：O(1)。
这个方法为什么说是投机取巧呢？直接看下图——
3、改进方案——快慢指针法
我们还有一种思路——
我们改进的思路是：找链表中间节点，将中间节点作为新链表的头节点，反转链表，遍历原链表，看看和反转1后的链表头节点的值是否相等。
我们来实现一下代码——
代码演示：
//稳妥法
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//找中间节点
ListNode* middleNode(ListNode* head)
{
//创建快慢指针
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
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 = n2->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
return n1;//链表的新的头节点
}
bool chkPalindrome(ListNode* A)
{
//1、找中间节点
ListNode* mid = middleNode(A);
//2、反转以中间节点为头的链表
ListNode* right = reverseList(mid);
//3、遍历原链表和反转后的链表，比较节点的值是否相等
ListNode* left = A;
while (right)
{
if (left->val != right->val)
{
return false;
}
left = left->next;
right = right->next;
}
return true;
}
};复杂度：时间复杂度：O(N)，空间复杂度：O(1)。
仔细观察代码，是不是用到了快慢指针、中间节点、反转链表这几个我们前几道题目用到的思路？
这就是我们前文书说过的卖的那个关子啦——
结尾
往期回顾：
【LeetCode&数据结构】单链表的应用——反转链表问题、链表的中间节点问题详解
【LeetCode】用双指针解决移除元素问题、合并两个有序数组求解
【LeetCode】力扣题——轮转数组、消失的数字、数组串联
结语：本篇文章到这里就结束了，本文讲述的两道代码题并不适合C语言初学者，需要有一定的C语言基础，最好要学过数据结构与算法的算法复杂度和链表的知识，才能写出复杂度较优的代码来。大家一定要自己动手敲一敲，不敲的话不仅容易忘记，也不方便将来复习。