做境外的网站网站违法么,qq官方网页版登录,企业常见问题及解决方案,长丰网站建设每日一题(LeetCode)----链表–分隔链表
1.题目#xff08;86. 分隔链表#xff09;
给你一个链表的头节点 head 和一个特定值 x #xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初…每日一题(LeetCode)----链表–分隔链表
1.题目86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1 输入head [1,4,3,2,5,2], x 3
输出[1,2,2,4,3,5]示例 2
输入head [2,1], x 2
输出[1,2]提示
链表中节点的数目在范围 [0, 200] 内-100 Node.val 100-200 x 200
2.解题思路
思路一
将这个链表进行拆分然后合并
1.拆分
把比目标值小的节点存一个链表里把比目标值大的节点另一个链表里
2.合并
把存比目标值大的节点的链表接到存比目标值小的节点的链表的后面
思路二快排的思想区间分割法
1.申请一个虚拟节点且这个虚拟节点指向头节点然后这个虚拟节点作为小区间(比目标值小的节点的空间)的尾节点
2.遍历链表进行节点的改变来得到所要的答案链表
遍历链表看当前链表中的值是否小于目标值
如果大于那么pre指向当前节点然后继续遍历
如果小于那么看pre所指向的节点是否是小区间的尾节点
如果是那么pre指向当前节点然后继续遍历
如果不是 (1)我们让pre指向的那个节点的下一个节点变为为当前节点的下一个节点
(2)当前节点指向小区间尾节点的下一个节点然后小区间的尾节点再指向当节点 (3)小区间的尾节点向后移动一个节点下一次要遍历的节点为pre所指向节点的下一个节点
3.写出代码
思路一的代码
class Solution {
public:ListNode* partition(ListNode* head, int x) {if(headnullptr||head-nextnullptr){return head;}//遍历一遍链表拆成两个链表ListNode* head1nullptr;ListNode* head2nullptr;ListNode* tail1nullptr;ListNode* tail2nullptr;while(head){if(head-valx){if(head1nullptr){head1tail1head;}else{tail1-nexthead;tail1tail1-next;}}else{if(head2nullptr){head2tail2head;}else{tail2-nexthead;tail2tail2-next;}}headhead-next;}if(tail1){tail1-nextnullptr;}if(tail2){tail2-nextnullptr;}if(tail1){tail1-nexthead2;return head1;}else{return head2;}}
};思路二的代码
class Solution {
public:ListNode* partition(ListNode* head, int x) {if(head nullptr || head-nextnullptr){return head;}ListNode* dummyhead new ListNode(0,head);ListNode* prevtail dummyhead,*prev dummyhead,*curr head;while(curr){if(curr-val x){if(prev ! prevtail){prev-next curr-next;curr-next prevtail-next;prevtail-next curr;prevtail prevtail-next;curr prev-next;}else{prev prevtail curr;curr curr-next;} }else{prev curr;curr curr-next;}}return dummyhead-next;}
};
