86 分隔链表

本文最后更新于：2021年1月21日 下午

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

1
2
输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

Solution

  • 建立两个链表，分别存储大于等于 x 的节点和小于 x 的节点
  • 借助虚拟头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummyHead1 = new ListNode(-1);
        ListNode* dummyHead2 = new ListNode(-1);
        ListNode* pre1 = dummyHead1;
        ListNode* pre2 = dummyHead2;

        for(ListNode* cur = head; cur!=NULL;){
            if(cur->val<x){
                pre1->next = cur;
                cur = cur->next;
                pre1 = pre1->next;
                pre1->next = NULL;
            }
            else{
                pre2->next = cur;
                cur = cur->next;
                pre2 = pre2->next;
                pre2->next = NULL;
            }
        }
        pre1->next = dummyHead2->next;
        ListNode* ret = dummyHead1->next;
        delete dummyHead1;
        delete dummyHead2;
        return ret;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！