题解 | #链表分割#

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) {} };/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNodelessHead,lessTail,greaterHead,greaterTail; //开一个哨兵位头结点，方便尾插 lessHead=lessTail=(struct ListNode)malloc(sizeof(struct ListNode)); lessTail->next=NULL; greaterHead=greaterTail=(struct ListNode)malloc(sizeof(struct ListNode)); greaterTail->next=NULL; struct ListNodecur=pHead; while(cur) { if(cur->val<x) { lessTail->next=cur; lessTail=cur; } else { greaterTail->next=cur; greaterTail=cur; } cur=cur->next; } lessTail->next=greaterHead->next; greaterTail->next=NULL; struct ListNodenewHead=lessHead->next; free(lessHead); free(greaterHead); return newHead; } };