首页 > 试题广场 > 链表分割
[编程题]链表分割
  • 热度指数:47052 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前

给定一个链表的头指针 ListNode* pHead,请返回重新排列后的链表的头指针。注意:分割以后保持原来的数据顺序不变。

推荐
思路

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

代码
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 回复(14)
Ron头像 Ron
/*定小数链表和大数链表,最后完成后将两链表连接,注意头结点也有值,
需要进行比较*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
    	if(pHead == null || pHead.next == null)
    	{
    		return pHead;
    	}
        ListNode cur = pHead;
        ListNode Shead = new ListNode(-1);
        ListNode Bhead = new ListNode(-1);
        ListNode Stmp = Shead;
        ListNode Btmp = Bhead;
        while(cur != null){
        	if(cur.val < x){
        		Stmp.next = new ListNode(cur.val);
        		Stmp = Stmp.next;
        	}else{
        		Btmp.next = new ListNode(cur.val);
        		Btmp = Btmp.next;
        	}
        	cur = cur.next;
        }
        cur = Shead;
        while(cur.next != null && cur.next.val != -1){
        	cur = cur.next;
        }
        cur.next = Bhead.next;
        return Shead.next;
    }
}

编辑于 2015-08-31 16:22:48 回复(19)
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* small=new ListNode(0);
        ListNode* large=new ListNode(0);
        ListNode* smallHead=small;
        ListNode* largeHead=large;
        while(pHead){
            if(pHead->val<x){
                small->next=pHead;
                small=small->next;
            }
            else{          
                large->next=pHead;
                large=large->next;
            }
            
            pHead=pHead->next;
                
        }
        large->next=NULL;

       small->next=largeHead->next;
       return smallHead->next;
        
    }
};

发表于 2016-04-05 15:48:56 回复(2)


public class Partition {
    public static ListNode partition(ListNode pHead, int x) {
        if(pHead==null || pHead.next==null) //如果为空,或者只有一个节点直接返回
           return pHead;
        ListNode maxHead = new ListNode(1);//定义大于等于的头节点
        ListNode minHead = new ListNode(0);//定义小于的头节点
        ListNode posMax = maxHead;//定义一个大于等于的链表 指针,指向当前位置
        ListNode posMin = minHead;//定义一个小于的链表 指针,指向当前位置        
           while(pHead!=null)
            {
                while(pHead!=null&&pHead.val<x)
                    {
                        posMin.next = pHead;  
                        posMin = posMin.next;//指针后移
                        pHead = pHead.next;
                        posMin.next = null;//断开与下一位的连接
                    }
                while(pHead!=null&&pHead.val>=x)//之所以判断为空是为了避免全部为小于x时,执行到这再调用val会报空指针
                    {
                        posMax.next = pHead;
                        posMax = posMax.next;
                        pHead = pHead.next;
                        posMax.next = null;
                    }
            }
            if(minHead.next==null)
                return    maxHead.next;
            if(maxHead.next!=null)
                 posMin.next = maxHead.next;
             return minHead.next;        
    }

}

编辑于 2015-09-23 01:04:37 回复(0)

题目分析:

要是链表换作数组要特别小心,因为搬迁数组要涉及到移动元素的开销,而移动链表的元素则容易很多,我们不需要移动和交换链表中的元素,只是改变一下每个节点的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)

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)
// 你可以在一个链表上玩,可以刚出来。
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 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)
将其分成两个链表,再合起来   注意考虑   全部小于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)
/*
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)
新建两个头指针,一个负责指向小于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)
 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)