)
思路很简单，将小于x的插入到small链表中，大于等于x的插入到large链表，最后将small插到large前面，返回small的头节点。但是插入的步骤很繁琐，需要设置头节点，甚至尾结点，在这里我们使用哨兵头节点来提高效率，减少繁琐容易搞乱的操作：
class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode smallDummy(0); ListNode largeDummy(0); ListNode* small=&smallDummy; ListNode* large=&largeDummy; ListNode* cur=head; while(cur){ if(cur->val<x){ small->next=cur; small=cur; } else{ large->next=cur; large=cur; } cur=cur->next; } large->next=nullptr; small->next=largeDummy.next; return smallDummy.next; } };哨兵头节点可以不受任何约束，并且可以保存链表的头节点，十分方便
