题解 | #链表分割#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //这里带哨兵位
        struct ListNode*greaterhead,*greatertail,*lesshead,*lesstail;
        lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
       greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greatertail->next=NULL;
        lesstail->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*head=lesshead->next;
         free(greaterhead);
         free(lesshead);
         return head;
    }
};