题解 | #链表分割#

#（1）首先创建四个节点lessHead,greaterHead,lessTail,greaterTail #（2）遍历整个链表，比x小的尾插到lessHead为哨兵位的那个链表，比x大的尾插到greaterHead为哨兵位的那个链表 #（3）把两个链表连接起来 #（4）创建一个list节点指向这个链表 #（5）把greaterTail->next置空，避免成环 #（6）释放lessHead,greaterHead #（7）返回list /* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) {} };/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* lessHead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greaterHead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* lessTail=lessHead; struct ListNode* greaterTail=greaterHead; lessTail->next=NULL; greaterTail->next=NULL; struct ListNode* cur=pHead; while(cur) { if(cur->val<x) { lessTail->next=cur; lessTail=lessTail->next; } else { greaterTail->next=cur; greaterTail=greaterTail->next; } cur=cur->next; } lessTail->next=greaterHead->next; greaterTail->next=NULL; struct ListNode* list=lessHead->next; free(lessHead); free(greaterHead); return list; }

};