LeetCode 86 分割链表
🟡 中等 https://leetcode.cn/problems/partition-list/description/
使用cur从链表中去掉大于等于x的节点。将去掉的节点使用尾插法 构建新链表，最后拼接。
- while 条件是 ：
while(cur->next!=nullptr){，而非cur!=nullptr因为下面会执行cur = cur->next的操作。我们要最后 cur 停留在最后一个，并且while中会执行 ++ 操作，因此判断条件中要”提前“终止。 cur->next = cur->next->next;和big_end->next = nullptr;顺序不能反；如果先执行后面的 那么 执行后cur->next->next就是nullptr了，这就丢失了原本的cur->next->next。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* fake_head = new ListNode();
fake_head->next = head;
ListNode* cur = fake_head;
ListNode* big_front = new ListNode();
ListNode* big_end = big_front;
while(cur->next!=nullptr){
if(cur->next->val>=x){
big_end->next = cur->next;
big_end = big_end->next;
cur->next = cur->next->next;
big_end->next = nullptr;
}else{
cur = cur->next;
}
}
cur->next = big_front->next;
return fake_head->next;
// return big_front->next;
}
};