题目
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
解法1：哨兵节点，在原链表挑小数节点到辅助链表里
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (NULL == head || NULL == head->next)
return head;
ListNode small(0), big(0);
ListNode *ptrSmall = &small, *ptrBig = &big;
big.next = head; //在big链表里挑小数节点到small链表里
while(ptrBig->next) {
if (ptrBig->next->val >= x) {
ptrBig = ptrBig->next;
} else {
ptrSmall->next = ptrBig->next;
ptrSmall = ptrSmall->next;
ptrBig->next = ptrBig->next->next;
}
}
ptrSmall->next = big.next;
return small.next;
}
};
解法2：直接处理原链表，小数节点放一个辅助链表，大数链表放一个辅助链表
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (NULL == head || NULL == head->next)
return head;
ListNode small(0), big(0);
ListNode *s = &small, *b = &big;
while (head) { //直接处理原链表
if (head->val < x) {
s->next = head;
s = s->next;
} else {
b->next = head;
b = b->next;
}
head = head->next;
}
s->next = big.next;
b->next = NULL; //注意尾节点置空，否则可能会出现环
return small.next;
}
};
