自己的做法
算法思想
创建两个节点，less_head, greater_head。代表比x小的节点链表和大于等于x的节点链表。
两个指针less和greater始终指向上述两个链表的尾节点。
使用cur指针遍历链表，如果小于x则添加到less_head中，否则添加到greater_head中。
添加后，将next指针置为空。
最后将两个链表连接起来即可。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode * less_head = new ListNode();
ListNode * greater_head = new ListNode();
ListNode * less = less_head;
ListNode * great = greater_head;
ListNode * cur = head;
while (cur != nullptr) {
ListNode * next = cur->next;
if(cur->val < x) {
less->next = cur;
less = less->next;
} else {
great->next = cur;
great = great->next;
}
cur->next = nullptr;
cur = next;
}
less->next = greater_head->next;
return less_head->next;
}
};
|
性能分析
时间复杂度: O(n)。
空间复杂度: O(1)。
另一种做法
算法思想
创建哑节点dummy，less指向所以小于x节点链表的尾节点，使用cur指针遍历链表，当cur的值小于x时，就将它添加到less后面，然后cur向后走一步。并且因为待添加节点要和后面节点断开，所以需要保持一个pre指针时时指向cur的上一个节点。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode * dummy = new ListNode();
dummy->next = head;
ListNode * less = dummy;
ListNode * cur = head;
ListNode * pre = dummy;
while (cur != nullptr) {
if(cur->val < x && less->next != cur) {
pre->next = cur->next;
cur->next = less->next;
less->next = cur;
less = less->next;
cur = pre;
} else {
pre = cur;
cur = cur->next;
}
}
return dummy->next;
}
};
|
性能分析
同上。
参考解法是第一种解法。