上海市建设工程合同备案网站,国外常用的seo站长工具,广告公司创意取名,网页设计心得体会学会了什么 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录链表OJ题(六)1. 链表… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录链表OJ题(六)1. 链表分割思路一 带哨兵位的头结点思路二 不强行加头结点7.总结上一篇链表OJ题链接【链表OJ题(五)】合并两个有序链表
链表OJ题(六)
1. 链表分割
链接CM11 链表分割
描述 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。
思路一 带哨兵位的头结点
题目要求我们将小于 x 的节点和大于等于 x 的节点分隔小于 x 的节点在前大于等于 x 的节点在后且不能改变原来的数据顺序。
不能改变顺序就比较棘手如果没有这个条件我们可以用双指针来写。但是题目既然给出了要求我们就得想办法解决。
我们创建一个新链表存放小于 x 的值另一个存放大于等于 x 的值。然后遍历原链表将符合条件的值放入对应的链表中最后再将存放小于 x 的值的链表和存放大于等于 x 的值的链表链接起来。
那么这过程肯定是尾插本题使用哨兵位是十分合适的因为本题有很多的空指针处理的情况所以我们设定两个哨兵位 lessHead 、 greaterHead。
再给定两个尾lessTail 、 greaterTail用来尾插。 但是最后记得释放哨兵位。
注意如果以 greaterHead 结束的元素不是链表的最后一个元素(即原链表最后一个元素小于 x )就可能会造成 链表带环 的情况,因为尾插改变前一个链接关系没有改变自己的后一个链接关系所以需要断开环然后将 greaterTail 的 next 置为空。
代码 class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessTail, *lessHead, *greaterTail, *greaterHead;// 建立哨兵位lessTail lessHead (struct ListNode*)malloc(sizeof(struct ListNode));greaterTail greaterHead (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur pHead;while (cur){if (cur-val x){lessTail-next cur;lessTail cur;}else{greaterTail-next cur;greaterTail cur;}cur cur-next;}// 链接两个链表lessTail-next greaterHead-next;greaterTail-next NULL; // 断开环// 拷贝节点释放哨兵位struct ListNode* ans lessHead-next;free(lessHead);free(greaterHead);return ans;}
};思路二 不强行加头结点
这道题目不用哨兵位也可以做但是比较考验细节
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessTail, *lessHead, *greaterHead, *greaterTail;lessTail lessHead greaterHead greaterTail NULL;struct ListNode* cur pHead;while (cur){if (cur-val x){if (lessTail NULL){// 第一次尾插lessHead lessTail cur;}else{lessTail-next cur;lessTail lessTail-next;}cur cur-next;}else{if (greaterTail NULL){// 第一次尾插greaterHead greaterTail cur;}else{greaterTail-next cur;greaterTail greaterTail-next;}cur cur-next;}}// lessHead 为空说明原链表为空或链表的值全大于 x// 且链表尾部的 next 一定为空// 返回 greaterHeadif (lessHead NULL)return greaterHead;// 如果 lessHead 和 greaterHead 都不为空// 说明正常分割// 将其链接greaterHead 尾部链空if (lessHead ! NULL greaterHead ! NULL){lessTail-next greaterHead;greaterTail-next NULL;}// 无论是正常分割还是链表的值全小于 x// 都是返回 lessHeadreturn lessHead;}
}; 7.总结
今天我们通过两种思路分析并完成链表分割这道链表OJ题目也更加深层次了解和使用了哨兵位的头结点这个思路通过这道题我们也能总结出当面对尾插且需要处理很多空指针的时候用哨兵位的头节点这个思路很方便。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
