题解 | #划分链表#

题目描述:给出一个长度为 nn 的单链表和一个值 xx ，单链表的每一个值为 list[i]list[i]，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

示例1
       输入：{1,4,3,2,5,2},3
       返回值：{1,2,2,4,3,5}
思路：直接遍历单链表两次，第一次将小于x的节点取出来放到新的单链表中，第二次遍历将大于等于x的节点取出来添加到新单链表后即可。具体代码如下：

/**
 * 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
        ListNode *res = (ListNode *)malloc(sizeof(ListNode)),*p=res,*q = head;
        while(q != NULL)
        {
            if(q->val < x)
            {
                ListNode *r = (ListNode *)malloc(sizeof(ListNode));
                r->val = q->val;
                r->next = NULL;
                p->next = r;
                p = p->next;
            }
            q = q->next;
        }
        q = head;
        while(q != NULL)
        {
            if(q->val >= x)
            {
                ListNode *r = (ListNode *)malloc(sizeof(ListNode));
                r->val = q->val;
                r->next = NULL;
                p->next = r;
                p = p->next;
            }
            q = q->next;
        }
        return res->next;
    }
};