题解 | #链表分割#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//总体思路：创建两个新链表，把比x小的放在第一个链表，把比x大的放在第二个链表，放节点的时候两个都相当于是链表的尾插，等全部元素放完之后把第一个链表和第二个链表相连，返回新链表，需要注意的是，要把第二个链表尾部置空，不然会会形成循环链表。
#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lesshead, 
        *lesstail,*bigerhead,
        *bigertail,
        *cur = pHead;
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lesshead->next = NULL;
        bigerhead = bigertail = (struct ListNode*)malloc(sizeof(struct ListNode));
        bigerhead->next = NULL;
        while(cur)
        {
            if(cur->val < x)
            {
                lesstail->next = cur;
                lesstail = cur;

            }
            else
            {
                bigertail->next = cur;
                bigertail = cur;
            }
            cur = cur->next;
        }
            
             lesstail->next = bigerhead->next;
             bigertail->next = NULL;
             struct ListNode* newhead = lesshead->next;
             free(lesshead);
             free(bigerhead);
             
             return newhead;

    }
};