题解 | #链表分割#

题目：给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。 解题思路： 1、将所有小于x的结点排在其余结点之前且不改变原来的数据顺序 将小于x的节点尾插到第一个链表，大于或等于x的节点尾插到第二个链表，最后将第一个链表的尾节点链接第二个链表的头节点 2、两个链表头部都malloc哨兵位节点 否则第一个链表可能为空，则需要判断

/*
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 *firstHead,*firstTail,*secondHead,*secondTail;
     firstHead = firstTail = (struct ListNode* )malloc(sizeof(struct ListNode));   
     secondHead = secondTail = (struct ListNode* )malloc(sizeof(struct ListNode));
     ListNode*cur = pHead;
     while(cur)
     {
        if(cur->val < x)            //小于x放入第一个链表
        {
            firstTail->next = cur;
            firstTail = firstTail->next;
        }
        else                        //否则放入第二个链表
        {
            secondTail->next = cur;
            secondTail = secondTail->next; 
        }
            cur = cur->next;
     }
        secondTail->next = NULL;      
        firstTail->next = secondHead->next;
        pHead = firstHead->next;
        free(firstHead);
        free(secondHead);
        return pHead;
}