链表OJ习题（1）
链表OJ习题（1）
用户11861691
发布于 2025-10-13 15:10:07
发布于 2025-10-13 15:10:07
代码可运行
运行总次数：0
代码可运行
一. leetcode 203 移除链表元素
迭代法
https://leetcode.cn/problems/remove-linked-list-elements/description/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode* pcur=head;
ListNode* newHead,*newTail;
newHead=newTail=NULL;
while(pcur)
{
if(pcur->val!=val)
{
if(newHead==NULL)
{
newHead=newTail=pcur;
}
else
{
newTail->next=pcur;
newTail=newTail->next;
}
}
pcur=pcur->next;
}
if(newHead)
newTail->next=NULL;
return newHead;
}思路
- 遍历原链表，筛选出不等于目标值的节点
- 将筛选出的节点依次连接，形成新链表
- 最后为新链表的尾节点next指针置空，避免链表循环
解题过程
- 定义newHead和newTail指针，分别指向新链表的头和尾
- pcur找到val不为指定的val值时，有两种情况：
- 1）新链表为空时，要将newHead和newTail都指向当前节点
- 2）新链表非空时，newHead作为新链表的头结点，无需做任何处理，将当前节点尾插到新链表末尾，newTail指向链表新的尾节点
- pcur跳出循环有两种情况
- 1）初始链表为空链表，这时可以直接返回newHead
- 2）初始链表不是空链表，pcur一直遍历到为空，要记得将newTail的next指针置为空，防止连接到后面的节点
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
二. leetcode 206 反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
法一：头插法
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
ListNode* pcur=head;
ListNode* newHead,*headNext;
newHead=headNext=NULL;
while(pcur)
{
ListNode* next=pcur->next;
if(newHead==NULL)
{
newHead=headNext=pcur;
headNext->next=NULL;
}
else
{
//头插
newHead=pcur;
newHead->next=headNext;
headNext=newHead;
}
pcur=next;
}
return newHead;
}思路
- 用headNext记录新的头结点newHead的下一个节点
- 每次循环先保存下一个节点，然后将原链表的节点头插到新链表中
- 移动指针继续遍历，最终newHead成为新表头
法二：迭代法
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
ListNode* prev=NULL;
ListNode* pcur=head;
while(pcur)
{
ListNode* next=pcur->next;
pcur->next=prev;
prev=pcur;
pcur=next;
}
return prev;
}思路
- 用prev记录前节点
- 每次循环先保存下一个节点，再将当前节点的next指针指向prev节点
- 移动指针继续遍历，最终prev成为新表头
解题过程
- 先创建两个指针，pcur和prev
- pcur用来遍历原链表，prev用来保存pcur节点的前一个节点
- 在遍历时，再创建next指针用来存储pcur节点的下一个节点，将pcur的next指针指向改变后，pcur继续遍历，跳出循环后prev即为新链表的头节点
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
三. leetcode 876 链表的中间节点
https://leetcode.cn/problems/middle-of-the-linked-list/description/
法一：计数法
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
//节点个数
ListNode*pcur=head;
int count=0;
while(pcur)
{
count++;
pcur=pcur->next;
}
int mid=count/2;
ListNode* midNode=head;
while(mid--)
{
midNode=midNode->next;
}
return midNode;
}思路
- 第一次遍历链表记录节点总个数
- 第二次遍历到中间节点返回该节点
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
法二：快慢指针法
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL && fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}思路
- 慢指针每次走一步，快指针每次走两步
- 快指针为空或快指针的下一个指针为空时，slow指针指向的节点即为中间节点
- 注意：循环条件中 fast!=NULL 必须放在前面。
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
四. leetcode 21 合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/description/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
ListNode*l1,*l2,*l3;
l1=list1;
l2=list2;
ListNode*newHead,*newTail;
newHead=newTail=(ListNode*)malloc(sizeof(ListNode));
//后面会用到newTail的next指针，所以需要初始化
newTail->next=NULL;
//l1用来遍历List1，l2用来遍历List2
while(l1!=NULL && l2!=NULL)
{
if(l1->val<l2->val)
{
newTail->next=l1;
newTail=newTail->next;
l1=l1->next;
}else{
newTail->next=l2;
newTail=newTail->next;
l2=l2->next;
}
}
//遍历完l2跳出循环
if(l1)
{
//将newTail的next指针指向l1可直接将l1后面的节点连接起来
newTail->next=l1;
}
//遍历完l1跳出循环
if(l2)
{
//将newTail的next指针指向l2可直接将l2后面的节点连接起来
newTail->next=l2;
}
ListNode* retNode=newHead->next;
//申请完空间要释放
free(newHead);
newHead=NULL;
return retNode;
}思路
- 创建虚拟头结点
- 创建两个指针分别遍历两个链表，每次取较小的节点接入新链表
- 拼接剩余未遍历完的链表
- 释放虚拟节点，返回新的链表头节点
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1）
五. 牛客网 链表分割
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
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;
}
greaterTail->next=NULL;
lessTail->next=greaterHead->next;
ListNode* ret=lessHead->next;
free(lessHead);
lessHead=NULL;
return ret;
}
};思路
- 定义两个哨兵节点（lessHead和greaterHead）,分别作为两个临时链表的头节点
- 遍历原链表，根究每个节点值的大小，将其插入到对应的链表的尾部
- 遍历结束后，要将保存大于x值节点的尾节点的next指针指向NULL，防止形成环
- 最后将保存小于x的链表的尾节点，与保存大于x值节点的头结点连接
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1）
总结
本篇博客深入解析了经典的链表OJ习题，旨在帮助读者掌握链表操作的核心技巧与解题思路，如快慢指针、双指针等。通过对典型例题的剖析，助你巩固数据结构基础。
如果大家在练习中发现新的解题角度，或是有没搞懂的知识点，欢迎在评论区留言讨论。后续我也会持续更新数据结构相关的 OJ 解析，咱们一起在刷题中夯实基础，稳步进阶！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-10-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
