找不到合适的词，就像qsort用一个叫partition的词一样，有没有合适的翻译呢，分裂？分堆？
做法也不难，就是两个链表，一个存小的，一个存大的，这样的好处就是在遍历原链表的时候不会破坏原始结构。
那么代码如下：
ListNode* partition(ListNode* head, int x) {
ListNode *less = new ListNode(0);
ListNode *more = new ListNode(0);
ListNode *l = less, *m = more;
ListNode *cur = head;
while(cur) {
if(cur->val < x) {
l = cur;
l = l->next;
} else {
m = cur;
m = m->next;
}
cur = cur->next;
}
l->next = more -> next; //唯一要注意的，more是m的head，指向它就好了
m->next = nullptr;
return less->next;
}
网友评论