給定一個(gè)鏈表和一個(gè)特定值 x雷厂，對(duì)鏈表進(jìn)行分隔钠糊，使得所有小于 x 的節(jié)點(diǎn)都在大于或等于 x 的節(jié)點(diǎn)之前专普。
你應(yīng)當(dāng)保留兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置蒂教。
示例:
輸入: head = 1->4->3->2->5->2, x = 3
輸出: 1->2->2->4->3->5
代碼
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy, *cur = head;;
while (pre->next && pre->next->val < x) pre = pre->next;
cur = pre;
while (cur->next) {
if (cur->next->val < x) {
ListNode *tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
pre = pre->next;
} else {
cur = cur->next;
}
}
return dummy->next;
}
};
