首页 > 试题广场 >

链表分割

[编程题]链表分割
  • 热度指数：114029 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

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


说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
推荐
念润头像 念润
思路

设置两个链表头，遍历原链表，一个追加小数链表，一个追加大数链表，最后将小数链表粘到大数链表前边即为结果。

代码 
class Partition {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr){
            return nullptr;
        }//if
        ListNode *smallList = new ListNode(-1);
        ListNode *bigList = new ListNode(-1);
        ListNode *ps = smallList,*pb = bigList,*cur = head;
        while(cur){
            if(cur->val < x){
                ps->next = cur;
                ps = cur;
            }//if
            else{
                pb->next = cur;
                pb = cur;
            }//else
            cur = cur->next;
        }//while
        pb->next = nullptr;
        ps->next = bigList->next;
        return smallList->next;
    }
};

编辑于 2015-10-04 19:17:59 回复(15)
C/C++
SamcYang头像 SamcYang
将其分成两个链表，再合起来   注意考虑   全部小于x 或 全部 大于等于x 的情况
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if (NULL == pHead) {
            return NULL;
        }
        ListNode *pFront = NULL,*pFrontTemp;
        ListNode *pLater = NULL,*pLaterTemp;
        ListNode *pTemp = pHead;
        while (pTemp) {
            if (pTemp->val < x) {
                if (NULL == pFront) {
                    pFront = pTemp;
                    pFrontTemp = pTemp;
                } else {
                    pFrontTemp->next = pTemp;
                    pFrontTemp = pTemp;
                }
            } else {
                if (NULL == pLater) {
                    pLater = pTemp;
                    pLaterTemp = pTemp;
                } else {
                    pLaterTemp->next=pTemp;
                    pLaterTemp = pTemp;
                }
            }
            pTemp = pTemp->next;
        }
        if (NULL == pFront) {
            pLaterTemp->next = NULL;
            return pLater;
        } else if ( NULL == pLater) {
            pFrontTemp->next = NULL;
            return pFront;
        } else {
            pFrontTemp->next = pLater;
            pLaterTemp->next = NULL;
            return pFront;
        }
    }
};
运行时间：5ms
占用内存：632k
发表于 2018-04-22 21:42:41 回复(0)
Python
华科平凡头像 华科平凡

python solution

class Partition:
    def partition(self, pHead, x):

        part1,part2=[],[]
        while pHead:
            if pHead.val<x:
                part1.append(pHead.val)
            else:
                part2.append(pHead.val)
            pHead=pHead.next

        dummy=ListNode(0)
        pre=dummy
        for i in part1+part2:
            node=ListNode(i)
            pre.next=node
            pre=pre.next
        return dummy.next
发表于 2017-10-31 15:38:58 回复(0)
Java
加勒比海涛头像 加勒比海涛 
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode head, int x) {
        // write code here
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        //定义两个区间段,把比x小的放在bs~be之间,比x大的放在as~ae之间
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur != null) {
            if(cur.val < x) {
                //是不是第一次插入
                //默认as ae都是在区间最前面的,然后我们选择让ae动,来标识前半段最后面的节点
                if(bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            } else {
                //同上
                if(as == null) {
                    //第一次插入
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //如果第一个区间段到最后也没数据,直接返回第二个区间段
        if(bs == null) {
            return as;
        }
        be.next = as;//把他们俩连接在一起
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
}

发表于 2022-06-25 23:29:19 回复(0)
峰峰的牛客头像 峰峰的牛客 
//思路：创建一个新的链表，以x为分割线，遍历原来的链表，将比x小的放在左边，大的放在右边
public ListNode partition(ListNode pHead,int x){
        //链表没有节点的时候直接返回null
        if(pHead==null){
            return null;
        }
        //链表只有一个节点的时候直接返回那个节点
        if(pHead.next==null){
            return pHead;
        }
        //创建x节点作为分割前半部分和后半部分的中间节点
        ListNode nodex=new ListNode(x);
        //创建newHead方便第一个小于x值的插入
        ListNode newHead=new ListNode(0);
        newHead.next=nodex;
        //创建before结点，在迭代过程中始终保持before.next=nodex
        //从而保证小于x值的结点可以插入到nodex结点之前
        ListNode before=newHead;
        //创建after结点，在迭代过程中始终保持after结点是最后一个结点
        //从而保证大于等于x值的结点可以插入链表的最后位置
        ListNode after=nodex;
        ListNode walk=pHead;
        while(walk!=null){//开始遍历原链表
            //如果当前节点小于x，复制结点并将其插入到xnode的前一个结点，然后移动before指针
            if(walk.val<x){
                ListNode node=new ListNode(walk.val);
                before.next=node;
                node.next=nodex;
                before=node;
            }
            //如果当前节点大于x，复制结点并将其插入到链表最后一个结点，然后移动after指针
            else if(walk.val>=x){
                ListNode node=new ListNode(walk.val);
                after.next=node;
                after=node;
            }
            walk=walk.next;
        }
        //这里要忽略自建的x结点nodex和头结点newHead，因为x结点不一定存在于原链表，所以此处要将分开的前后部分相连
        before.next=nodex.next;
        return newHead.next;
    }

编辑于 2019-11-28 15:39:53 回复(0)
C/C++
但求八月九月好运！头像 但求八月九月好运！ 
//试来试去，只有重新建立一个链表的方法比较快O（n）
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if(pHead==nullptr||pHead->next==nullptr) return pHead;
        ListNode *ans=new ListNode(0);
        ListNode *p=ans;
        ListNode *q=pHead;
            //如果要调换小于x、大于x、等于x的顺序那么可以调整下面三者循环的顺序
        while(q!=nullptr)
        {
            if(q->val<x)
            {
                ListNode *temp=new ListNode(q->val);
                p->next=temp;
                p=temp;
            }
            q=q->next;
        }
        q=pHead;
        while(q!=nullptr)
        {
            if(q->val>x)
            {
                ListNode *temp=new ListNode(q->val);
                p->next=temp;
                p=temp;
            }
            q=q->next;
        }
        q=pHead;
        while(q!=nullptr)
        {
            if(q->val==x)
            {
                ListNode *temp=new ListNode(q->val);
                p->next=temp;
                p=temp;
            }
            q=q->next;
        }
        return ans->next;
    }
};

发表于 2019-05-02 15:33:40 回复(0)
每日一格头像 每日一格 
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode dummyHead1 = new ListNode(0);
        ListNode dummyHead2 = new ListNode(0);
        ListNode p1 = dummyHead1;
        ListNode p2 = dummyHead2;
        while (pHead != null) {
            if (pHead.val < x) {
                p1.next = pHead;
                p1 = p1.next;
            }
            else {
                p2.next = pHead;
                p2 = p2.next;
            }
            pHead = pHead.next;
        }
        p2.next = null;// prevent [x+1, x-1, x-2]
        p1.next = dummyHead2.next;
        
        return dummyHead1.next;
    }
}

发表于 2019-01-20 17:13:39 回复(1)
木然猫猫头像 木然猫猫 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if (!pHead) { return pHead; }
        ListNode* p = new ListNode(-1);
        ListNode* q = new ListNode(-1);
        ListNode* ph = p;
        ListNode* qh = q;
        while (pHead) {
            if (pHead->val < x) {
                p->next = pHead;
                p = p->next;
            } else {
                q->next = pHead;
                q = q->next;
            }
            pHead = pHead->next;
        }
        q->next = nullptr;  // 这步需要有，否则超内存
        qh = qh->next;
        p->next = qh;
        return ph->next;
    }
};

运行时间：5ms

占用内存：604k


发表于 2018-12-23 20:20:29 回复(0)
蓝魔4头像 蓝魔4 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if(pHead==NULL)
            return pHead;
        queue<int> smallx;
        queue<int> bigx;
        ListNode* p=pHead;
        while(p)
        {
            if(p->val<x)
                smallx.push(p->val);
            else
                bigx.push(p->val);
            p=p->next;
        }
        p=pHead;
        while(p)
        {
            if(!smallx.empty())
            {
                p->val=smallx.front();
                smallx.pop();
            }
            else
            {
                p->val=bigx.front();
                bigx.pop();
            }
            p=p->next;
        }
        return pHead;
    }
};

发表于 2017-07-24 11:09:50 回复(0)
阿狸不是猫头像 阿狸不是猫 
 import java.util.*;
//把链表分成大于X和小于X的两个表
//再合并
//数据结构没学好，也不知道这个效率怎么样

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
		//创建两个新的链表节点
        ListNode leftNode = new ListNode(0);
        ListNode rightNode = new ListNode(0);
        ListNode head =leftNode;
        ListNode rhead =rightNode;
       	//分解原链表
        while(pHead !=null){
            if(pHead.val < x){
		leftNode.next = pHead;
                leftNode = leftNode.next;
            }else{
		rightNode.next =pHead;
                rightNode= rightNode.next;
            }
            pHead=pHead.next;
        }
        //合并新的两个链表
        leftNode.next=rhead.next;
        rightNode.next =null;
        return head.next;  
    }
}
运行时间：213ms
占用内存：3111k

发表于 2017-05-16 17:36:44 回复(0)
Java
村长，那人偷牛！头像 村长，那人偷牛！ 
//直接排序，简单暴力
 public ListNode partition(ListNode pHead, int x) {
        if(pHead==null) return null;
        final int n=x;
        ArrayList<ListNode> sortNode=new ArrayList<ListNode>();
        ListNode cur=pHead;
        ListNode result=new ListNode(0);
        ListNode dummy=result;
        while(cur!=null){
            sortNode.add(cur);
            cur=cur.next;
        }
        Collections.sort(sortNode,new Comparator<ListNode>(){
            public int compare(ListNode node1,ListNode node2){
               if(node1.val>=n&&node2.val<n) return 1;
               else if(node2.val>=n&&node1.val<n) return -1;
               else return 0;
            }
        });
        for(ListNode temp:sortNode) {
            dummy.next=temp;
            dummy=dummy.next;;
        }
        dummy.next=null;
        return result.next;
    }

发表于 2017-05-11 20:50:33 回复(0)
绝对凌度头像 绝对凌度
最简单的一个思路： 
    public static ListNode partition(ListNode pHead, int x) {
        ArrayList<Integer> less = new ArrayList<>();
        ArrayList<Integer> eq = new ArrayList<>();
        ArrayList<Integer> more = new ArrayList<>();
        while (pHead != null){
            if(pHead.val == x){
                eq.add(pHead.val);
            }else if(pHead.val > x){
                more.add(pHead.val);
            }else{
                less.add(pHead.val);
            }
            pHead = pHead.next;
        }
        less.addAll(more);
        less.addAll(eq);
        pHead = null;
        ListNode p = null;
        for (Integer a :less) {
            if(pHead == null){
                p = pHead = new ListNode(a);
            }else{
                p.next = new ListNode(a);
                p = p.next;
            }
        }
        return pHead;
    }

发表于 2017-05-01 08:52:43 回复(0)
Java
❤pep_G头像 ❤pep_G 
分析：（1）创建两个链表，把大于等于x的放到链表2,小于x的放到链表1


	        （2）将两个链表拼接起来





	


//用java写，实在不高效
public class Partition {
	ListNode testHead=null;
	ListNode testTail=null;
	//2.创建新链表需要的元素:
	//@1两个链表的头节点
			 
	ListNode head1=null;
	ListNode head2=null;
	//3.创建操作元素
	ListNode tail1=null;
	ListNode tail2=null;
	public ListNode partition(ListNode pHead, int x) {
        // write code here
		//1.接收链表头的第一个节点
		ListNode current=pHead;
	/*	while(pHead!=null){
		System.out.print(pHead.val+"  ");
		pHead=pHead.next;
		//testHead=testHead.next;
	}*/
		while(current!=null){
			//如果小于x，则装入链表1,
			if(current.val<x){
				insert1(current.val);
				//如果大于或等于x,则装入链表2
			}else{
				insert2(current.val);
			}
			//下一个链表节点
			current=current.next;
		}
		//对两链表进行拼接
		if(head1==null&&head2==null){
			return null;
		}else if(head1==null&&head2!=null){
			return head2;
		}else if(head1!=null&&head2==null){
			return head1;
		}else{
			//两链表拼接
			tail1.next=head2;
			return head1;
		}
		
	}
	public void insert1(int result){
		//首先创建一个新节点
		ListNode node=new ListNode(result);
		if(head1==null){
			head1=node;
			tail1=node;
			System.out.println("链表1  "+head1.val+"  ");
		}else{
			tail1.next=node;
			tail1=node;
		}
	}
	public void insert2(int result){
		//首先创建一个新节点
		ListNode node=new ListNode(result);
		if(head2==null){
			head2=node;
			tail2=node;
			System.out.println("链表2  "+head2.val+"  ");
		}else{
			tail2.next=node;
			tail2=node;
		}
	}

发表于 2017-04-12 11:30:40 回复(0)
亦心谷头像 亦心谷 
//分割链表，分别新增大小两个链表，最后合起来即可
public ListNode partition(ListNode pHead, int x) {
		ListNode smallPre = new ListNode(-1);
        ListNode bigPre = new ListNode(-1);
        ListNode sHead = smallPre;
        ListNode bHead = bigPre;
        while (pHead != null) {
            if (pHead.val < x) {
            	smallPre.next = pHead;
            	smallPre = smallPre.next;
            } else {
            	bigPre.next = pHead;
            	bigPre = bigPre.next;
            }
            pHead = pHead.next;
        }
        smallPre.next = bHead.next;
        bigPre.next = null;
        return sHead.next;
    }

发表于 2017-04-03 13:25:44 回复(0)
java是我儿子头像 java是我儿子
这个标记头指针和尾指针  用的是和快排一样的思路
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
ListNode pHead1 = new ListNode(x);
ListNode pFirst = pHead1;
ListNode pLast = pHead1;
ListNode ptemp = pHead;
while(ptemp != null) {
if(ptemp.val < x) {
if (pFirst.next == null) {
pFirst.next = new ListNode(ptemp.val);
                    pFirst = pFirst.next;
pLast = pLast.next;
} else {
ListNode temp = pFirst.next;
pFirst.next = new ListNode(ptemp.val);
pFirst = pFirst.next;
pFirst.next = temp;
}
} else {
pLast.next = new ListNode(ptemp.val);
pLast = pLast.next;
}
ptemp = ptemp.next;
}
return pHead1.next;
    }
}
发表于 2017-02-16 17:17:53 回复(0)
已注销头像 已注销 
//先用笨方法写一下，时间复杂度0（n），空间复杂度0(n);
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(pHead==NULL || pHead->next==NULL) return NULL;
        ListNode* p=pHead;
        vector<int> vec;
        int i=0;
        while(p!=NULL)
        {
            if(p->val<x)
                vec.push_back(p->val);
            p=p->next;
        }
        p=pHead;
        while(p!=NULL)
        {
            if(p->val>=x)
                vec.push_back(p->val);
            p=p->next;
        }
        p=pHead;
        while(p!=NULL)
        {
            p->val=vec[i];
            i++;
            p=p->next;
        }
        return pHead;
    }
};

发表于 2016-08-06 17:24:57 回复(0)
Python
Yannyezixin头像 Yannyezixin
思路：
迭代访问链表， 用一个新链表链接小于x的结点，另一个新链表链接大于x的结点。最后链接两个链表，返回第一个新链表的头结点即可 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Partition:
    def partition(self, pHead, x):
        if not pHead:
            return None
        
        dummybefore = before = ListNode(0)
        dummyafter = after = ListNode(0)
        
        while pHead:
            if pHead.val < x:
                before.next = pHead
                before = before.next
            else:
                after.next = pHead
                after = after.next
            pHead = pHead.next
            
        after.next = None
        before.next = dummyafter.next
        return dummybefore.next

发表于 2016-08-02 08:52:08 回复(1)
从前从前有个人爱你很久头像 从前从前有个人爱你很久 
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {			//注意这里有构造函数!!
        this.val = val;
    }
}*/
//思路:扫描两边遍，第一遍接小于x的,第二遍接大于等于x的
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode head = new ListNode(-1);		//保留头结点
        ListNode p = pHead;
        ListNode h = head;
        while(pHead != null){
            if(pHead.val < x){
                h.next = new ListNode(pHead.val);		//新建一个节点接在后面
                h = h.next;
            }
            pHead = pHead.next;
        }
        while(p != null){
            if(p.val >= x){
                h.next = new ListNode(p.val);
                h = h.next;
            }
            p = p.next;
        }
        return head.next;
    }
}

发表于 2016-07-11 18:20:32 回复(1)
MichaelTim头像 MichaelTim 
//在原来链表上操作
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        int count = 0;
        vector<int> array;
        if(pHead == NULL) return pHead;
        ListNode* pCurNode = pHead;
        ListNode* pHighNode = pHead;
        while(NULL != pCurNode){
            if(pCurNode->val < x) count++;
            array.push_back(pCurNode->val);
            pCurNode = pCurNode->next;
        }
        for(int i = 0; i < count; i++){
            pHighNode = pHighNode->next;
        }
        int siz = array.size();
        pCurNode = pHead;
        for(int i = 0; i < siz; i++){
            if(array[i] < x){
                pCurNode->val = array[i];
                pCurNode = pCurNode->next;
            }
            else{
                pHighNode->val = array[i];
                pHighNode = pHighNode->next;
            }
        }
        return pHead;
    }
};

发表于 2016-05-08 22:48:28 回复(1)
masteryi123头像 masteryi123
这个更加难调试，可以看看咯。
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
		ListNode **p = &pHead;
		ListNode *cur = pHead;
		ListNode *bHead = pHead;
		ListNode **q = &bHead;
		pHead = NULL;

		while (cur) {
			if (cur->val < x) {
				*q = cur->next;

				cur->next = *p;
				*p = cur;
				p = &(*p)->next;
			}
			else {
				q = &(*q)->next;
			}
            cur = *q;
		}
		*q = *p;
		*p = bHead;
		return pHead;
    }
};

发表于 2016-05-06 10:09:16 回复(0)
Pis头像 Pis
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
ListNode* front=new ListNode(0);
ListNode* f;
f=front;
ListNode* tail=new ListNode(0);
ListNode* t;
t=tail;
ListNode* p;
p=pHead;
while(p!=NULL)
{
ListNode* tmp=new ListNode(p->val);
if(p->val<x)
{
front->next=tmp;
front=front->next;
}
else
{
tail->next=tmp;
tail=tail->next;
}
p=p->next;
}
front->next=t->next;
return f->next;

    } 
};

发表于 2015-12-18 10:45:11 回复(0)
提交观点

问题信息

编程基础 链表
难度：
199条回答 51349浏览

热门推荐

通过挑战的用户

查看代码

相关试题

链表分割

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号