分隔链表精美图示哦
引言
前面,我们熟悉了管理链表中的数据的方法,也了解了几道与链表相关的题目:
戳我看单链表详解哦
分隔链表
题目描述与思路
这道题要求我们实现将一个点链表中,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;
}
总结
到此,关于分隔链表的介绍就结束了。
接下来会继续介绍链表的相关知识,欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题,欢迎大家在评论区提出
如果本文对你有帮助,希望一键三连哦
希望与大家共同进步哦
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgcikae
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13