🔥个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向：C/C++方向
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述，我们进入今天的力扣题目介绍——
目录
正文
一、移除链表元素问题
博主题解链接：创建新链表再尾插解决移除链表元素问题
推荐大家可以直接去看博主在力扣上面写的题解，介绍的还是比较详细的。
题目描述：
1、思路
我们的思路是：创建新链表，再把原链表中不为val的节点拿到新链表尾插。
2、解题过程
像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。
如下图所示——
我们创建一个新的链表，再在新的链表里面尾插值不为val的节点，最后返回新的链表，即得到了删除链表中等于给定值 val 的所有节点——
接下来我们实现一下这个程序——
3、代码演示
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
//创建新链表
ListNode* newHead,*newTail;
newHead = newTail = NULL;
ListNode* pcur = head;
while(pcur)
{
//判断pcur节点的值是否为val
if(pcur->val != val)
{
//尾插
if(newHead == NULL)
{
//链表为空
newHead = newTail = pcur;
}
else
{
//链表非空
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
if(newTail)
newTail->next = NULL;
return newHead;
}复杂度：时间复杂度：O(N)，空间复杂度：O(1)。
二、 链表分割问题详解
这道题是牛客网上面的题目，因为也是链表专题的，博主就一并放到LeetCode专栏了。
本题的牛客网链接：链表分割
由于本题是牛客网的题，博主还没在牛客网写过题解，所以不放题解链接了，这题博主会细讲。
题目描述：
1、思路
我们先想想可以怎么做，简单分析一下题目——
我们的思路是：创建两个链表（大链表、小链表），遍历原链表，小的尾插到小链表中，大的尾插到大链表中，大链表和小链表首尾相连。
2、解题过程
还是那句话，画图，一定要有这个意识，数据结构的算法题一定要画图。
如下图所示——
我们想让它首尾相连， 根据我们的思路可以尝试写一下代码了——
代码演示：
//自测通不过
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
//创建两个带头的空链表
ListNode* lessHead, * lessTail;
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* greaterHead, * greaterTail;
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* pcur = pHead;
while (pcur) {
if (pcur->val < x)
{
lessTail->next = pcur;
lessTail = lessTail->next;
}
else {
greaterTail->next = pcur;
greaterTail = greaterTail->next;
}
pcur = pcur->next;
}
//大链表尾节点的next指针置为NULL（避免死循环）
greaterHead->next = NULL;
//大小链表首尾相连
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(lessHead);
free(greaterHead);
return ret;
}
};对不对呢？我们自己输入一些值自测一下——
当然还可能存在这种错误，不过这个跟内存超限没什么关系：
这个问题出在下图这里——
不要写成greaterHead， 那就要报错了。
3、改进方案
原因如下图所示——
程序死循环了，我们把大链表尾节点的next指针置为空指针，就可以避免死循环——
我们改进之后，再自测一下——
代码演示：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
//创建两个带头的空链表
ListNode* lessHead,*lessTail;
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
ListNode*greaterHead,*greaterTail;
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
ListNode* pcur = pHead;
while(pcur){
if(pcur->val < x)
{
lessTail->next = pcur;
lessTail = lessTail->next;
}
else {
greaterTail->next = pcur;
greaterTail = greaterTail->next;
}
pcur = pcur->next;
}
//大链表尾节点的next指针置为NULL（避免死循环）
greaterTail->next = NULL;
//大小链表首尾相连
lessTail->next = greaterHead->next;
ListNode* ret = lessHead->next;
free(lessHead);
free(greaterHead);
return ret;
}
};复杂度：时间复杂度：O(N)，空间复杂度：O(1)。
结尾
往期回顾：
【牛客&LeetCode&数据结构】单链表的应用——合并两个有序链表问题、链表的回文结构问题详解
【LeetCode&数据结构】单链表的应用——反转链表问题、链表的中间节点问题详解
【LeetCode】用双指针解决移除元素问题、合并两个有序数组求解
【LeetCode】力扣题——轮转数组、消失的数字、数组串联
结语：本篇文章到这里就结束了，本文讲述的两道代码题并不适合C语言初学者，需要有一定的C语言基础，最好要学过数据结构与算法的算法复杂度和链表的知识，才能写出复杂度较优的代码来。大家一定要自己动手敲一敲，不敲的话不仅容易忘记，也不方便将来复习。