首页 > 试题广场 >

链表分割

[编程题]链表分割
  • 热度指数:106028 时间限制: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)

题目分析:

要是链表换作数组要特别小心,因为搬迁数组要涉及到移动元素的开销,而移动链表的元素则容易很多,我们不需要移动和交换链表中的元素,只是改变一下每个节点的next指针就可以,我们可以创建两个链表,一个链表是存放小于x的元素,另一个链表存放大于等于x的元素,然后遍历一遍原有链表,将小于x元素的节点加到第一个链表上,将大于等于x元素的节点加到第二个链表上。便可实现分割。
《程序员面试金典》题目详解:http://blog.csdn.net/zdplife/article/category/5799903

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
		ListNode* beforeStart=NULL;
		ListNode* beforeEnd=NULL;
		ListNode* afterstart=NULL,*afterEnd=NULL;
		ListNode* headval;
		while(pHead)
		{
			headval=pHead->next;
			if(pHead->val<x)
			{
				if(beforeEnd==NULL)
					beforeEnd=beforeStart=pHead;
				else
				{
					beforeEnd->next=pHead;
					beforeEnd=pHead;
				}
			}
			else
			{
				if(afterstart==NULL)
				{
					afterstart=afterEnd=pHead;
				}
				else
				{
					afterEnd->next=pHead;
					afterEnd=pHead;
				}
			}
			pHead=headval;
		}
		if(afterEnd)
			afterEnd->next=NULL;
		if(beforeEnd!=NULL)
			beforeEnd->next=afterstart;
		else
			beforeStart=afterstart;
		return beforeStart;
    }
};

编辑于 2015-09-21 20:39:49 回复(3)
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) {
        
        if(pHead == null){
            return pHead;
        }
        ListNode small = new ListNode(-1);
        ListNode big = new ListNode(-1);
        ListNode smallHead = small;
        //分别设置头指针指向两个链表的首节点
        ListNode bigHead = big;
        ListNode curNode = pHead;
        
        while(curNode != null){
            if(curNode.val < x){
               small.next =  curNode;
               small = small.next;
            }else{
                big.next = curNode;
                big = big.next;
            }
            curNode = curNode.next;
        }
        //small链表最后一个节点指向big的头指针,即bigHead
        small.next = bigHead.next;
        //big链表最后一个节点设置为尾节点,即设置为null
        big.next = null;
        
        //返回small链表的头指针
        return smallHead.next;
        
    }
}

发表于 2017-03-13 18:32:01 回复(0)
将其分成两个链表,再合起来   注意考虑   全部小于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 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)
//空间也为O(1)
class Partition {
public:
	ListNode* partition(ListNode* pHead, int x) {
		// write code here
		if (pHead == NULL) return pHead;

		int cnt = 1; 
		ListNode* rear = pHead;
		while (rear->next != NULL) {         //找到尾以及长度
			rear = rear->next;
			cnt++;
		}

		ListNode* newHead = new ListNode(0); //临时头结点,避免特殊处理
		newHead->next = pHead;

		ListNode* curNode = newHead;
		while (cnt--) {                      //遍历,遇到大于等于x的就往后链表后移动
			ListNode* tmp = curNode->next;
			if (tmp->val >= x) {
				curNode->next = tmp->next;
				tmp->next = NULL;
				rear->next = tmp;
				rear = tmp;
			}
			else curNode = curNode->next;
		}
		ListNode* realhead = newHead->next;  //删除临时头结点
		delete newHead;
		return realhead;
	}
};

发表于 2017-08-17 17:39:56 回复(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)
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)
/*
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)
// 用两个链表指针解决。最后要注意链表的末尾要设置好。
// 算法的时间复杂度O(n),空间复杂度O(1)
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode node = pHead;
    	ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        ListNode newHead = left;
        ListNode rightHead = right;
        while(node != null) {
            if(node.val < x) {
                left.next = node;
                left = left.next;
            } else {
                right.next = node;
                right = right.next;
            }
            node = node.next;
        }
        left.next = rightHead.next;
        right.next = null;
        return newHead.next;
    }
}

编辑于 2017-03-02 14:15:20 回复(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)