当前位置：首页 > news >正文

分隔链表（精美图示详解哦）

news 2025/9/12 22:32:03

全文目录

引言
分隔链表
- 题目描述与思路
- 实现
总结

引言

前面，我们熟悉了管理链表中的数据的方法，也了解了几道与链表相关的题目：
戳我看单链表详解哦

在本篇文章中，我们将再了解一道题目：分隔链表：
分隔链表OJ链接

分隔链表

题目描述与思路

在这里插入图片描述
这道题要求我们实现将一个点链表中，val大于等于x的结点与val小于x的结点分隔：小于x的结点在大于x的结点前。并且原链表中的数据顺序不能发生改变。
即，若链表数据为1、4、3、2、5、2，x=3时，分隔后的链表为：1、2、2、4、3、5。

输入两个参数：链表的首结点地址head与分隔标准x。结构体变量与主函数部分已经定义，我们只需要实现接口即可。

不难想到，只要遍历整个链表，然后将val小于x的结点尾插到一个链表中，将val大于等于x的结点尾插到一个链表中。遍历结束后，再将两个链表连接起来即可。
又由于直接尾插时，当链表为空时，处理会比较麻烦，且还需要判断链表是否为空。用有哨兵位头结点的链表尾插即可：

实现

为了使代码更简洁，我们可以对结构体名称重命名：

typedef struct ListNode ListNode;

为实现这个算法，我们首先需要一个结构体指针cur，并将其初始化为head，用来遍历单链表：

ListNode* cur = head;

然后，我们需要4个指针，分别为val小于x的结点存放的链表的头结点地址与尾结点地址；val大于等于x的结点存放的链表的头节点地址与尾结点地址。将他们全部初始化为NULL：

ListNode* above = NULL;
ListNode* low = NULL;
ListNode* abovetail = NULL;
ListNode* lowtail = NULL;

然后，动态开辟两个哨兵位头节点的空间并断言其是否成功开辟：

above = abovetail = (ListNode*)malloc(sizeof(ListNode));
low = lowtail = (ListNode*)malloc(sizeof(ListNode));
assert(above && low);

然后，在将两链表头结点的next成员都初始化为NULL后（防止有某一链表为空时出现问题），就可以开始遍历了。

while循环遍历整个链表，条件为cur不为空：
若cur->val < x：
将lowtail->next改为cur，即连接low链表的尾结点与cur。然后lowtail=lowtail->next，即让lowtail指针向后移动一个结点，继续指向链表的尾结点。然后cur=cur->next，即cur向后移动一位；
若cur-> <= x：
将abovetail->next改为cur，即连接above链表的尾结点与cur。然后abovetail=abovetail->next，即让abovetail指针向后移动一个结点，继续指向链表的尾结点。然后cur=cur->next，即cur向后移动一位。
在这里插入图片描述

遍历结束后，lowtail->next = above->next，即将above链表连接到low链表的后面。然后abovetail->next = NULL，即，将连接后的链表的尾结点的next成员改为NULL：

最后，free释放动态开辟的两块内存空间。但是由于释放后就不能返回值，所以先用一个ret指针记录low->next的值，等释放low与above指向的空间后，返回ret即可：
在这里插入图片描述

struct ListNode* partition(struct ListNode* head, int x)
{typedef struct ListNode ListNode;ListNode* cur = head;ListNode* above = NULL;ListNode* low = NULL;ListNode* abovetail = NULL;ListNode* lowtail = NULL;above = abovetail = (ListNode*)malloc(sizeof(ListNode));low = lowtail = (ListNode*)malloc(sizeof(ListNode));assert(above && low);above->next = low->next = NULL;while (cur){if (cur->val < x){lowtail->next = cur;lowtail = lowtail->next;cur = cur->next;}else{abovetail->next = cur;abovetail = abovetail->next;cur = cur->next;}}lowtail->next = above->next;abovetail->next = NULL;ListNode* ret = low->next;free(low);free(above);return ret;
}