🔥个人主页:艾莉丝努力练剑
❄专栏传送门:《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语言基础,最好要学过数据结构与算法的算法复杂度和链表的知识,才能写出复杂度较优的代码来。大家一定要自己动手敲一敲,不敲的话不仅容易忘记,也不方便将来复习。