博客

链表分割_牛客题霸_牛客网 (nowcoder.com)

题目：

现有一链表的头指针 ListNode*

pHead

，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：

把data小于x的结点摘下来，放到一个新的链表，再将旧的链表接上去。

一共需要5个指针

1、newListHead :新链表的头结点

2、oldListHead: 旧链表的头结点

3、newNext:新链表指向下一个结点的指针

4、oldNext:旧链表指向下一个结点的指针

5、cur:指向当前操作的结点

代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        
        ListNode* newListHead =NULL;
        ListNode* oldListHead =NULL;
        ListNode* newNext =NULL;
        ListNode* oldNext =NULL;
        
        
        while(pHead)
        {
            if(pHead->val < x)//第一个小于x或者大于x的结点为newListhHead/oldListHead
            {
                if(NULL ==newListHead )
                {
                    newNext = newListHead = pHead;

                }
                else
                {
                    newNext->next = pHead;
                    newNext = pHead;
                }
                
            }
            else
            {
                if(NULL ==oldListHead )
                {
                    oldNext = oldListHead = pHead;
                     
                }
                else
                {
                    oldNext->next = pHead;
                    oldNext = pHead;
                }
            }
            pHead =pHead->next;
            
        }
        if(oldNext)
        {
            oldNext->next = NULL;  
        }
        if(NULL == newListHead)
        {
            return oldListHead;
        }
        else
        {
            newNext->next = oldListHead;
            return newListHead;
        
        }

    }
};