题解 | #划分链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param x int整型 
 * @return ListNode类
 */

struct ListNode* remake( struct ListNode* listnode )
{
    struct ListNode* p = listnode;
    
    if( p->next == NULL ) return NULL;
    
    while( p->next->next != NULL )
    {
        p = p->next;
    }
    p->next = NULL;
    
    return listnode;
    
}


struct ListNode* partition(struct ListNode* head, int x ) 
{
    if( head == NULL ) return NULL;
    
    struct ListNode* p = head;
    
    struct ListNode* first = ( struct ListNode* )malloc( sizeof(struct ListNode) );
    struct ListNode* pfirst = first;            //用于保存小于x的链表
    pfirst->val = 0;
    pfirst->next = NULL;
    

    struct ListNode* second = ( struct ListNode* )malloc( sizeof(struct ListNode) );
    struct ListNode* psecond = second;        //用于保存大于等于x的链表
    psecond->val = 0;
    psecond->next = NULL;    
    
    while( p )
    {
        struct ListNode* new = ( struct ListNode* )malloc( sizeof(struct ListNode) );
        new->val = 0;
        new->next = NULL;
        if( p->val < x )
        {
            pfirst->val = p->val;            //创建两个列表分别存储小于x的节点，和大于等于x的节点
            pfirst->next = new;              //需要注意的是我们创建的列表默认有一个节点，如果遍历输入的链表之后，
            pfirst = new;                    //pfirst或者psecond 只有一个节点的时候，表示改链表其实为空，只有初始化的节点。
            pfirst->next = NULL;
        }
        else if( p->val >= x )
        {
            psecond->val = p->val;
            psecond->next = new;
            psecond = new;     
            psecond->next = NULL;
        }
        p=p->next;    
    }
    

    pfirst = remake( first );
    
    psecond = remake( second );
    
    
    if( psecond != NULL && pfirst == NULL ) return psecond;
    
    if( pfirst != NULL && psecond == NULL ) return pfirst;
    
    if( pfirst == NULL && psecond == NULL ) return NULL;
    
    
    struct ListNode* res = pfirst;
    while( pfirst->next != NULL )
    {
        pfirst = pfirst->next;
    }
    
    pfirst->next = psecond;
    
    return res;
}