题解 | #链表分割#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        int lowcount=0;
        int highcount=0;
        ListNode* cur=pHead;
        while(cur)  //判断是否有全小于x或全大于x的情况
        {
            if(cur->val<x)
            {
                lowcount++;
            }
            else {
                highcount++;
            }
            cur=cur->next;
        }
        if((lowcount==0)||(highcount==0))
        {
            return pHead;
        }
        ListNode*lowhead=NULL;          //创建小于x值的单链表
        ListNode*highhead=NULL;         //储存尾节点地址
        ListNode*lowend=NULL;           //创建大于x值的单链表
        ListNode*highend=NULL;          //储存尾节点的地址
        ListNode*tmp=pHead;
        while(tmp)
        {
            if(tmp->val<x)
            {
                if(lowhead==NULL)       //头结点为空时将小于x值节点的地址赋值给lowhead和lowend
                {
                    lowhead=lowend=tmp;
                }
                else {
                    lowend->next=tmp;       //将小于x值节点的地址尾接到lowend的后面
                    lowend=tmp;             //lowend后移一位
                }
                }
            else
            {
                if(highhead==NULL)      //头结点为空时将大于x值节点的地址赋值给highhead和highend
                {
                    highhead=highend=tmp;
                }
                else {
                    highend->next=tmp;      //将不小于x值节点的地址尾接到highend的后面
                    highend=tmp;            //highend后移一位
                }
            }
            tmp=tmp->next;
        }
        highend->next=NULL;             //将高值链表尾节点的next置空
        lowend->next=highhead;          //链接高值链表和低值链表
        return lowhead;                 //返回低值链表的头节点
    }
};