86. 分隔链表
其实这个题多少ms已经没关系了，因为大家都是O(n)的时间复杂度。当然空间复杂度得是O(1)才更好，也就是不能生成新的链表作为答案，就用原链表返回。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *p = new ListNode(0);
p->next = head;
ListNode *left = p, *right = head;
head = p;
while (right) {
if (right->val < x) {
if (left == p) {
left = left->next;
p = p->next;
right = right->next;
} else {
p->next = right->next;
right->next = left->next;
left->next = right;
left = left->next;
right = p->next;
}
} else {
p = p->next;
right = right->next;
}
}
return head->next;
}
};
