现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
[编程题]链表分割
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)
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)
//试来试去，只有重新建立一个链表的方法比较快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)
/*
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)
/*
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)
//直接排序，简单暴力
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)
分析：（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)
这个标记头指针和尾指针 用的是和快排一样的思路
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)
思路：
迭代访问链表， 用一个新链表链接小于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)
//在原来链表上操作
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)
这个更加难调试，可以看看咯。
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)
// 你可以在一个链表上玩，可以刚出来。
public ListNode partition(ListNode pHead, int x) {
ListNode t, p, q , r; //t is the current partion node val < x, q is current node, p、q is adjacent
t = p = null;
q = pHead;
while (q != null) {
r = q.next;
if (q.val < x) {
if (t == null) {
if (q != pHead) // if q isn't the first node
q.next = pHead;
pHead = q;
t = q;
} else {
if (t.next != q) { // avoid deadlock
q.next = t.next; // insert after partion node
t.next = q;
}
t = q;
}
if (p != null)
p.next = r; // delete current node
} else
p = q;
q = r;
}
return pHead;
}
// 也可以另创俩链表，最后凑在一起。
public ListNode partition(ListNode pHead, int x) {
ListNode before, after, p, q, t;
t = pHead;
before = after = p = q = null;
while (t != null) {
if (t.val < x) {
if (before == null) {
p = before = t;
} else {
p.next = t;
p = t;
}
} else {
if (after == null) {
q = after = t;
} else {
q.next = t;
q = t;
}
}
t = t.next;
}
if (before == null)
return after;
p.next = after;
if (q != null)
q.next = null;
return before;
}
编辑于 2016-04-04 16:55:24
回复(0)
新建两个头指针，一个负责指向小于x的，一个负责指向大于x的，最后再把他们拼接起来就可以了
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode s1 = new ListNode(-1);
ListNode s2 = new ListNode(-2);
ListNode res1 = s1;
ListNode res2 = s2;
while(pHead!=null){
if (pHead.val<x) {
s2.next=null;
s1.next = pHead;
s1=pHead;
pHead=pHead.next;
}else {
s1.next = null;
s2.next = pHead;
s2=pHead;
pHead = pHead.next;
}
}
s1.next=res2.next;
return res1.next;
}
}
发表于 2017-06-14 10:19:07
回复(0)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if(pHead == null){
return pHead;
}
ListNode smallNode = new ListNode(-1);
ListNode bigNode = new ListNode(-1);
ListNode smallFirst, bigFirst;
smallFirst = smallNode;
bigFirst = bigNode;
//注意此处条件是pHead,如果是pHead.next会少判断一次，拉下了最后一个数
while(pHead != null){
if(pHead.val < x){
smallNode.next = pHead;
smallNode = pHead;;
}else{
bigNode.next = pHead;
bigNode = pHead;
}
pHead = pHead.next;
}
smallNode.next = bigFirst.next;
bigNode.next = null;
return smallFirst.next;
}
}
发表于 2015-08-28 10:40:30
回复(4)
问题信息
难度：
202条回答
402收藏
54187浏览
通过挑战的用户
查看代码-
2023-03-13 16:39:46 -
2023-03-13 14:31:31 -
2023-03-13 12:21:38
-
2023-03-12 21:21:42 -
2023-03-12 11:26:46
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
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; } };