现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
[编程题]链表分割
先将整个链表以x的值为标记分类，可以使用尾插的方法，然后分别对x值分割的前半段和后半段的数据进行判断
public class Partition {
public ListNode partition(ListNode head, int x) {
// write code here
if (head == null) {
return null;
}
ListNode cur = head;
ListNode bigHead = null;
ListNode bigLast = null;
ListNode smallHead = null;
ListNode smallLast = null;
while (cur != null) {
if (cur.val < x) {
if (smallHead == null) {
smallHead = cur;
smallLast = cur;
} else {
smallLast.next = cur;
smallLast = smallLast.next;
}
} else {
if (bigHead == null) {
bigHead = cur;
bigLast = cur;
} else {
bigLast.next = cur;
bigLast = bigLast.next;
}
}
cur = cur.next;
}
//1、如果前半段没有数据，就直接返回后半段
if (smallHead == null) {
return bigHead;
}
smallLast.next = bigHead;
//2、如果后半段不为空，就将最后一个节点的next置为null
if (bigHead != null) {
bigLast.next = null;
}
return smallHead;
}
}
发表于 2024-03-17 23:28:36
回复(0)
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
while (cur != null) {
if (cur.val < x) {
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;
}
编辑于 2023-12-02 10:24:06
回复(0)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
//分成两部分,两部分各自连接好了
while (cur != null) {
if (cur.val < x) {
if (bs == null) { //是第一个元素的情况
bs = cur;
be = cur;
} else {
be.next = cur;
be = cur;
}
} else {
if (as == null) { //是第一个元素的情况
as = cur;
ae = cur;
} else {
ae.next = cur;
ae = cur;
}
}
cur = cur.next;
}
//把这两部分连接起来
//还要考虑这两部分中 有一方不存在或者都不存在的情况
if (bs == null) {
return as;
}
be.next = as;//连接起来的操作
//注意尾巴
if(as != null) {
ae.next = null;
}
return bs;
}
}
发表于 2023-08-11 21:22:29
回复(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
if (pHead == null) {
return null;
}
ListNode cur = pHead;
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
while (cur != null) {
if (cur.val < x) {
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;
}
//1、bs == null
if (bs == null) {
return as;
}
be.next = as;
if (as != null) {
ae.next = null;
}
return bs;
}
}方法二
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
if (pHead == null || pHead.next == null) return pHead;
ListNode bH = null;
ListNode bT = null;
ListNode aH = null;
ListNode aT = null;
ListNode cur = pHead;
ListNode next = null;
while (cur != null) {
next = cur.next;
cur.next = null;
if (cur.val < x) {
if (bH == null) {
bH = cur;
bT = cur;
} else {
bT.next = cur;
bT = bT.next;
}
} else {
if (aH == null) {
aH = cur;
aT = cur;
} else {
aT.next = cur;
aT = aT.next;
}
}
cur = next;
}
//有小于x的节点
if (bT != null) {
bT.next = aH;
}
return bH != null ? bH : aH;
}
}
编辑于 2023-09-15 10:08:34
回复(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) {
if(head == null) return null;
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur =head;
while(cur != null){
if(cur.val< x){
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;
}
}
发表于 2023-03-22 12:40:11
回复(0)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if(pHead == null || pHead.next == null){return pHead;};
ListNode newHead = new ListNode(-1);
newHead.next = pHead;
ListNode cur = pHead;
ListNode p = newHead;
ListNode slow = newHead;
while(pHead != null && pHead.val < x ){ //处理头节点就是小于x的情况
pHead = pHead.next; //让最后一个小于x的充作newHead
cur = cur.next;
slow = slow.next;
p = p.next;
}
while(cur != null){
if(cur.val >= x){
cur = cur.next;
slow = slow.next;
}else{
slow.next = cur.next;
cur.next = pHead;
p.next = cur;
p = cur;
cur = slow.next;
}
}
return newHead.next;
}
}
发表于 2022-12-09 21:11:36
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
/**
思路：首先将整个链表分为2段，第一段的话采用两个引用变量(beforestart，beforeend)
第二段采用两个引用变量(afterstart,afterend)
之所以采用be和ae是因为题目要求要保证原来的数据顺序不能改变,
所以就要使用尾插法,而尾插法就要找到尾巴的位置,用be和ae去保存.
如果没有这两个变量，那么要想找到尾巴还需要再遍历链表,遍历链表就需要时间。
*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
//遍历整个链表,找到比x小的放到第一段,>=x的放到第二段.
//当 cur == null的时候，链表遍历完成.(cur != null的时候说明链表还没遍历完)
while(cur!=null){
if(cur.val <x){
//第一次插入节点
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;
}
//while循环走完说明链表遍历完成
//要进行判断，如果第一段或者第二段是没有数据的，可能会造成空指针异常
if(bs == null){
return as;
}
if(as != null){
ae.next = null;//如果原链表最后一个元素是小于x的,那么其next就不为null了，那么第二段的最后一个元素的next就需要手动置空，否则会造成死循环,堆溢出,系统找不到链表的尾巴了。
}
be.next = as;
return bs;
}
}
发表于 2022-11-22 15:10:38
回复(0)
public class Partition { public ListNode partition(ListNode pHead, int x) { if(pHead == null) { return null; } ListNode pos = pHead;//用于遍历 ListNode fhead = null;//前半的头 ListNode fcur = null;//前半的连接点 ListNode bhead = null;//后半的头 ListNode bcur = null;//后半的连接点 while(pos != null) { if(pos.val < x) { //第一次插入 - 保持头不动 if(fhead == null) { fhead = pos; fcur = pos;//这里要与fhead关联上 }//不是第一次插入 else { fcur.next = pos; fcur = fcur.next; } }//同上 else { if(bhead == null) { bhead = pos; bcur = pos; } else { bcur.next = pos; bcur = bcur.next; } } pos = pos.next; } //如果全是大于 x 的 if(fhead == null && bhead != null) { bcur.next = null; return bhead; } //如果全是小于 x 的 else if(fhead != null && bhead == null) { //手动制空 fcur = null; }//正常情况 else { fcur.next = bhead; bcur.next = null; } return fhead; } }
发表于 2022-09-19 13:03:14
回复(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)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode bs=null;
ListNode be=null;
ListNode as=null;
ListNode ae=null;
ListNode cur=pHead;
while(cur!=null){
if(cur.val<x){
if(bs==null){
bs=cur;
be=cur;
}else{
be.next=cur;
be=cur;
}
}else{
if(as==null){
as=cur;
ae=cur;
}else{
ae.next=cur;
ae=cur;
}
}
cur=cur.next;
}
if(bs==null){
return as;
}
be.next=as;
if(as!=null){
ae.next=null;
}
return bs;
}
}
发表于 2022-05-08 20:51:59
回复(0)
public class Partition {
public ListNode partition(ListNode head, int x) {
//1. 创建五个指针
//创建两个傀儡节点 newhead1 和 newhead2
//再创建这两个傀儡节点的替身，cur1，和 cur2
//创建一个指针 sign 用来遍历原来的链表
ListNode newhead1 = new ListNode(-1);
ListNode newhead2 = new ListNode(-2);
ListNode cur1 = newhead1;
ListNode cur2 = newhead2;
ListNode sign = head;
//2. 进行区间划分
//比 x 值小的放在前一个区间比 x 值大的放在后一个区间
while(sign != null){
if(sign.val < x){
cur1.next = sign;
cur1 = cur1.next;
sign = sign.next;
}else{
cur2.next = sign;
cur2 = cur2.next;
sign = sign.next;
}
}
//3. 傀儡节点失效，重新定义两个区间的头结点
newhead1 = newhead1.next;
newhead2 = newhead2.next;
//4. 连接两个区间
cur1.next = newhead2;
//5. 考虑特殊情况
if(newhead2 != null){
cur2.next = null;
}
if(newhead1 == null ){
return newhead2;
}
return newhead1;
}
}
发表于 2022-04-29 13:39:31
回复(0)
import java.util.*;
public class Partition {
public ListNode partition(ListNode head, int x) {
ListNode bs=null;
ListNode be=null;
ListNode as=null;
ListNode ae=null;
while(head!=null){
if(head.val<x){
if(bs==null){
bs=head;
be=head;
}else{
be.next=head;
be=be.next;
}
head=head.next;
}else{
if(as==null){
as=head;
ae=head;
}else{
ae.next=head;
ae=ae.next;
}
head=head.next;
}
}
if(bs==null){
return as;
}
if(as!=null){
ae.next=null;
}
be.next=as;
return bs;
}
}
发表于 2021-10-27 18:38:10
回复(0)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode h1 = new ListNode(-1);
ListNode h2 = new ListNode(-1);
ListNode one = h1;
ListNode two = h2;
for(ListNode cur = pHead; cur != null; cur = cur.next){
if(cur.val < x){
one.next = cur;
one = cur;
}else{
two.next = cur;
two = cur;
}
}
two.next = null;
one.next = h2.next;
return h1.next;
}
}
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode h1 = new ListNode(-1);
ListNode h2 = new ListNode(-1);
ListNode one = h1;
ListNode two = h2;
for(ListNode cur = pHead; cur != null; cur = cur.next){
if(cur.val < x){
one.next = cur;
one = cur;
}else{
two.next = cur;
two = cur;
}
}
two.next = null;
one.next = h2.next;
return h1.next;
}
}
发表于 2021-07-28 18:36:16
回复(0)
Java 实现，已通过。两个链表 ，最后串一起，代码如下：
import java.util.*;
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 less=null;
ListNode more=null;
ListNode moreHead=null;
ListNode lessHead=null;
while (pHead!=null)
{
if(pHead.val<x)
{if(less==null) {
lessHead = new ListNode(pHead.val);
less=lessHead;
}
else {
less.next = new ListNode(pHead.val);
less = less.next;
}
}
else
{if(more==null) {
moreHead= new ListNode(pHead.val);
more=moreHead;
}
else {more.next=new ListNode(pHead.val);
more=more.next;
}}
pHead=pHead.next;
}
if(less==null) {return moreHead;}
less.next=moreHead;
return lessHead;
}
}
发表于 2020-02-25 11:21:21
回复(0)
设置两个链表
一个存放val比x大的值
一个存放val比x小的值
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if(pHead == null || pHead.next == null) return pHead;
ListNode newHead = new ListNode(0);
ListNode flagHead = new ListNode(0);
ListNode newh = newHead;
ListNode flagh = flagHead;
while(pHead != null){
if(pHead.val < x){
newh.next = new ListNode(pHead.val);
newh = newh.next;
}else{
flagh.next = new ListNode(pHead.val);
flagh = flagh.next;
}
pHead = pHead.next;
}
newh.next = flagHead.next;
return newHead.next;
}
}
发表于 2020-02-24 08:00:42
回复(0)
模拟栈
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode left , right ,lTop , rTop; // 栈顶与栈底的定义
left = right = lTop = rTop = null;
while (pHead != null) {
if (pHead.val < x) {
if (lTop == null) left = lTop = pHead;
else left = left.next = pHead; // 小的入栈
} else {
if (rTop == null) right = rTop = pHead;
else right = right.next = pHead; // 大的入栈
}
pHead = pHead.next;
}
if (right != null) right.next = null;// 防止成环
if (left != lTop) left.next = rTop; // 小的和大的连接
return left != lTop ? lTop : rTop;
}
}
编辑于 2020-01-08 21:01:49
回复(0)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if(pHead == null || pHead.next == null){
return pHead;
}
ListNode pCur = pHead;
ListNode lHead = new ListNode(-1);
ListNode hHead = new ListNode(-1);
ListNode lCur = lHead;
ListNode hCur = hHead;
while(pCur != null){
if(pCur.val < x){
lCur.next = new ListNode(pCur.val);
lCur = lCur.next;
}else{
hCur.next = new ListNode(pCur.val);
hCur = hCur.next;
}
pCur = pCur.next;
}
lCur = lHead;
while(lCur.next != null && lHead.next != null){
lCur = lCur.next;
}
if(hHead.next != null){
lCur.next = hHead.next;
}
return lHead.next;
}
}
发表于 2018-11-20 17:37:54
回复(0)
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if(pHead == null){
return null;
}
ListNode cur = pHead;
ListNode small = new ListNode(10);
ListNode large = new ListNode(10);
ListNode s = small;
ListNode l = large;
while(cur!=null){
ListNode temp = new ListNode(cur.val);
if(cur.val<x){
s.next = temp;
s = s.next;
}else{
l.next = temp;
l = l.next;
}
cur = cur.next;
}
cur = small;
while(cur.next!=null){
cur = cur.next;
}
cur.next = large.next;
return small.next;
}
}
发表于 2017-06-23 13:49:26
回复(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)
问题信息
难度：
24条回答
402收藏
54257浏览
通过挑战的用户
查看代码-
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; } };