## [Leetcode]86. Partition List(C++)

### 题目描述

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

### 例子

#### 例子 1

Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]

#### 例子 2

Input: head = [2,1], x = 2 Output: [1,2]

### Constraints

• The number of nodes in the list is in the range [0, 200].
• -100 <= Node.val <= 100
• -200 <= x <= 200

### 解题思路

class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* less_list = new ListNode();
ListNode* less_tail = less_list;
ListNode* greater_list = new ListNode();
ListNode* greater_tail = greater_list;
ListNode* curr = head;
while (curr) {
if (curr->val < x) {
less_tail->next = curr;
less_tail = curr;
} else {
greater_tail->next = curr;
greater_tail = curr;
}
curr = curr->next;
}
less_tail->next = greater_list->next;
return less_list->next;
}
};
• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 86.PartitionList.cpp

Built with Hugo
Theme Stack designed by Jimmy