题解 | #划分链表#

1.将链表中的每个值进行遍历；如果小于x则将器叠加到左侧，反之叠加在右侧；
2.使用L指针维护左侧队尾，队尾的下一个节点为首个大于x的节点
3.使用rh表示右侧首个节点指针，rt表示右侧对尾的最后一个指针，时刻维护。

/**

• struct ListNode {
• int val;
• struct ListNode *next;
• };
• /

class Solution {
public:
/*
*
* @param head ListNode类
* @param x int整型
* @return ListNode类
*/
ListNode partition(ListNode* head, int x) {
// write code here
//定义一个虚头;定义一个指针维护大于x的头
/*
1.将链表中的每个值进行遍历；如果小于x则将器叠加到左侧，反之叠加在右侧；
2.使用L指针维护左侧队尾，队尾的下一个节点为首个大于x的节点
3.使用rh表示右侧首个节点指针，rt表示右侧对尾的最后一个指针，时刻维护。

    */
    ListNode*H=new ListNode(0);
    ListNode* L=NULL,*rh=NULL,*rt=NULL;
    ListNode* h=H;
    while(head)
    {
        if(head->val<x)
        {
            //头节点下一个目标位小于x的节点值
            H->next=new ListNode(head->val);
            //更新H已经头节点，节点尾的下一个节点位第一个大于x的节点
            L=H->next;
            L->next=rh;
            H=L;
        }
        else
        {
            //表示首个右侧节点值
            if(!rh)
            {
                rh=new ListNode(head->val);
                //将大于的首个数字放在左尾
                if(L)//之前出现过小于x的值
                    L->next=rh;
                rt=rh;
            }
            else
            {
                //其他直接将其放置在rt之后进行叠加
                rt->next=new ListNode(head->val);
                rt=rt->next;
            }
        }
        head=head->next;
    }
    //若L为空表示只存在大于x的节点
    if(L==NULL) return rh;
    return h->next;
}

};