每日一題(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(head==nullptr||head->next==nullptr){return head;}//遍歷一遍鏈表拆成兩個鏈表ListNode* head1=nullptr;ListNode* head2=nullptr;ListNode* tail1=nullptr;ListNode* tail2=nullptr;while(head){if(head->val<x){if(head1==nullptr){head1=tail1=head;}else{tail1->next=head;tail1=tail1->next;}}else{if(head2==nullptr){head2=tail2=head;}else{tail2->next=head;tail2=tail2->next;}}head=head->next;}if(tail1){tail1->next=nullptr;}if(tail2){tail2->next=nullptr;}if(tail1){tail1->next=head2;return head1;}else{return head2;}}
};
思路二的代碼
class Solution {
public:ListNode* partition(ListNode* head, int x) {if(head ==nullptr || head->next==nullptr){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;}
};
