题解 | #链表分割#

class Partition {
public:
  	// 方法：
  	// 定义两个链表，一个存储比x大的节点，一个存储比x小的节点。
  	// 使用cur遍历链表，比x大就放到gt链表，比x小就放到lt链表。
  	// 最后将gt链表末尾置空（就是将cur_gt的next指针置空）。并将gt链表接到lt链表的后面。
  	// 拼接和返回的时候，都要注意略过头节点。
    ListNode* partition(ListNode* phead, int x) {
        ListNode* head_gt = new ListNode(-1), *cur_gt = head_gt;
        ListNode* head_lt = new ListNode(-1), *cur_lt = head_lt;
        ListNode* cur = phead;
        while (cur) {
            if (cur->val < x) {
                cur_lt->next = cur;
                cur_lt = cur_lt->next;
            } else {
                cur_gt->next = cur;
                cur_gt = cur_gt->next;
            }
            cur = cur->next;
        }
        cur_gt->next = nullptr;
        cur_lt->next = head_gt->next;
        return head_lt->next;
    }
};