首页 > 试题广场 >

划分链表

[编程题]划分链表

热度指数：33904 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个长度为 n 的单链表和一个值 x ，单链表的每一个值为 list_i ，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

例如：

给出 $1 \to 4 \to 3 \to 2 \to 5 \to 2$ 和 $x = 3$

返回 $1 \to 2 \to 2 \to 4 \to 3 \to 5$

数据范围： $n \le 200$ ， $-100 \le list[i] \le 100$

进阶：时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

示例1

输入

{1,4,3,2,5,2},3

输出

{1,2,2,4,3,5}

示例2

输入

{1,2,3,4,1},5

输出

{1,2,3,4,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

C/C++

JordanBelfort

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head == NULL) return head;
        ListNode* p1 = new ListNode(INT_MIN);
        ListNode* p2 = new ListNode(INT_MIN);
        ListNode* pp1 = p1;
        ListNode* pp2 = p2;
        ListNode* pNode = head;
        while(pNode != NULL) {
            if(pNode->val < x) {
                pp1->next = pNode;
                pp1 = pp1->next;
            }
            else {
                pp2->next = pNode;
                pp2 = pp2->next;
            }
            pNode = pNode->next;
        }
        pp2->next = NULL;
        pp1->next = p2->next;
        return p1->next;
    }
};

发表于 2017-03-10 16:35:20 回复(0)

猫丫

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null)
            return null;
        ListNode dummy1=new ListNode(0);
        ListNode dummy2=new ListNode(0);
        ListNode curr1=dummy1;
        ListNode curr2=dummy2;
        while(head!=null){
            if(head.val<x){
                curr1.next=head;
                curr1=curr1.next;
            }else{
                curr2.next=head;
                curr2=curr2.next;
            }
            head=head.next;
        }
        curr2.next=null;//这句很重要！链表最后一个元素如果小于x的话，那么curr2.next
不为null
        curr1.next=dummy2.next; 
        return dummy1.next; 
    }
}

发表于 2016-06-20 20:51:01 回复(7)

方块儿脑袋

不需要再创建新的链表哟

ListNode *partition(ListNode *head, int x) {
        // 添加dummynode
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *pre_less = dummyHead, *p = dummyHead;
        while (p->next) {
            if (p->next->val < x) {
                if (p->next == pre_less->next) {
                    pre_less = p->next;
                    p = p->next;
                } else {
                    ListNode *cur_less = p->next;
                    p->next = cur_less->next;
                    cur_less->next = pre_less->next;
                    pre_less->next = cur_less;
                    pre_less = pre_less->next;
                }
            } else {
                p = p->next;
            }
        }
        return dummyHead->next;
    }

发表于 2019-06-10 20:45:28 回复(2)

WordZzzz

看到的都是申请两个链表，先分后切。我这里贴出来我博客里面的，O(n)时间复杂度，O(1)空间复杂度。

转载请注明作者和出处：http://blog.csdn.net/u011475210
代码地址：https://github.com/WordZzzz/Note/tree/master/LeetCode
刷题平台：https://www.nowcoder.com/ta/leetcode
题库：Leetcode经典编程题
编者：WordZzzz

[toc]

题目描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given1->4->3->2->5->2and x = 3,
return1->2->2->4->3->5.

解题思路

牛客网上面的答案都是新建两个链表，小于x的放到一个链表里面，不小于的放到另一个链表里面，这种答案感觉好没劲哦。所以最后我采用的是O(n)时间复杂度，O(1)空间复杂度的解法。

具体说来，还是用快慢指针遍历链表，slow指向连续小于x的最后一个元素，fast指向当前元素不小于x但是下个元素小于x的元素。理解清楚这两个指针的对应关系之后，我们很容易将fast指向的元素的下一个元素追加到slow之后，同时更新slow和fast的指。

C++版代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head == NULL)
            return NULL;

        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *fast = dummy;
        ListNode *slow = dummy;
        while(fast != NULL && fast->next != NULL){
            if(fast->next->val >= x)
                fast = fast->next;
            else{
                if(fast == slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                else{
                    ListNode *tmp = fast->next;
                    fast->next = tmp->next;
                    tmp->next = slow->next;
                    slow->next = tmp;
                    slow = slow->next;

                }
            }
        }
        return dummy->next;
    }
};

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

发表于 2018-01-17 08:36:38 回复(3)

Butterfliesflyaway↘

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return null;
        if(head.next == null) return head;
        
        ListNode allMax = new ListNode(x); //用来存所有大于等于x的临时链表的头节点
        ListNode p1 = allMax;
        ListNode allMin = new ListNode(x); //用来存所有小于x的临时链表的头结点
        ListNode p2 = allMin;
        
        ListNode headNext = head.next;
        while(headNext != null) { //遍历传入的链表
            if(head.val >= x) { //将所有大于等于x的节点挂在allMax链后，移动p1实现
                p1.next = head;
                p1 = p1.next;
            } else { //将所有小于x的节点挂在allMin链后，移动p2实现
                p2.next = head;
                p2 = p2.next;
            }
            headNext = head.next;
            head.next = null; //要断开原链的链接关系
            head = headNext;
        }
        p2.next = allMax.next; //跨过allMax头结点，链接两个链表
        return allMin.next;
    }
}

发表于 2019-01-03 09:59:09 回复(0)

风被枯叶吹下

    ListNode *partition(ListNode *head, int x) {
        ListNode* p = head;
        vector<int> tmp;
        while(p!=NULL)
        {
            if(p->val < x)
                tmp.push_back(p->val);
            p = p->next;
        }
        p = head;
        while(p!=NULL)
        {
            if(p->val >= x)
                tmp.push_back(p->val);
            p = p->next;
        }
        p = head;
        for(int i = 0;i<tmp.size>val = tmp[i];
            p = p->next;
        }
        return head;
    }
</tmp.size></int>

    ListNode *partition(ListNode *head, int x) {
        ListNode* p = head;
        ListNode* LVal = new ListNode(0);
        ListNode* GVal = new ListNode(0);
        ListNode* tmpL = LVal;
        ListNode* tmpG = GVal;
        while(p!=NULL)
        {
            if(p->val < x)
            {
                ListNode* node = new ListNode(p->val);
                tmpL->next = node;
                tmpL = tmpL->next;
            }else{
                ListNode* node = new ListNode(p->val);
                tmpG->next = node;
                tmpG = tmpG->next;
            }
            p = p->next;
        }
        tmpL->next = GVal->next;
        return LVal->next;
    }

第一种解法用数组记录数值，然后改变按顺序改变每一个节点的值，没用改变或新建任何一个节点。

第二种解法遍历节点的时候，用Lval记录比X值要小的节点，Gval记录比X值要大的节点，然后连接这两个链表。

第一种解法时间和空间使用上都更少一些。

编辑于 2018-08-20 20:52:34 回复(1)

顾翅

用了个蠢方法，在原链表上操作。

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head==NULL)
            return head;
        ListNode *dummy=new ListNode(-100000);
        dummy->next=head;
        ListNode* insert=dummy;
        ListNode*cur=head;
        ListNode*pre=dummy;
        while(cur){
            if(cur->val<x&&pre->val>=x){
                ListNode*temp=cur->next;
                pre->next=cur->next;
                cur->next=insert->next;
                insert->next=cur;
                cur=temp;
                insert=insert->next;
            }else if(cur->val<x&&pre->val<x){
                insert=cur;
                pre=cur;
                cur=cur->next;
            }
            else{
                pre=cur;
                cur=cur->next;
            }
        }
        return dummy->next;
    }
};

发表于 2018-06-18 20:44:12 回复(0)

quwhsk

import java.util.*;

public class Solution {
    /*
        思路：将这张链表拆分成两张一小一大的链表，再将这两种链表链接起来
    */
    public ListNode partition (ListNode head, int x) {
        //    首先创建两个哑节点，这样能够统一插入操作的代码
        ListNode dummy_small = new ListNode(0), dummy_other = new ListNode(0);
        //    不直接修改哑节点的指向，因此使用cur_xxx指针代替
        ListNode cur_small = dummy_small, cur_large = dummy_other;
        //    从头到尾遍历一次链表，小于x的挂在cur_small后面
        //    大于x的挂在cur_large后面
        while(head != null){
            if(head.val < x){
                cur_small.next = head;
                cur_small = head;
            }else{
                cur_large.next = head;
                cur_large = head;
            }
            head = head.next;
        }
        //    最后将两张链表拼接起来
        //    【这里需要注意的是，是将小的链表的最后节点指向大的链表的头节点，而不是最后的节点】
        cur_small.next = dummy_other.next;
        //    大的链表最后节点的指向应该置为null
        cur_large.next = null;

        return dummy_small.next;
    }
}

发表于 2021-11-15 14:57:19 回复(0)

Spectre_

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        ListNode *smallHead = NULL, *smallTail = NULL;
        ListNode *bigHead = NULL, *bigTail = NULL;
        while (head) {
            if (head->val < x) {
                if (smallHead == NULL) {
                    smallHead = head;
                    smallTail = head;
                } else {
                    smallTail->next = head;
                    smallTail = head;
                }
            } else {
                if (bigHead == NULL) {
                    bigHead = head;
                    bigTail = head;
                } else {
                    bigTail->next = head;
                    bigTail = head;
                }
            }
            head = head->next;
        }
        if (smallTail == NULL && bigTail == NULL) return NULL;
        if (smallTail == NULL) return bigHead;
        if (bigTail == NULL) return smallHead;
        smallTail->next = bigHead;
        bigTail->next = NULL;
        return smallHead;
    }
};

发表于 2021-09-14 20:07:13 回复(0)

tuweilong

/*
链表真的太烦了。
要加强对象和引用的理解以及区分。
*/
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode list1 = new ListNode(0);
        ListNode list2 = new ListNode(0);
        ListNode cur1 = list1, cur2 = list2;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                cur1.next = cur;
                cur1 = cur1.next;
            } else {
                cur2.next = cur;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        cur1.next = list2.next;
        cur2.next = null;
        return list1.next;
    }
}

发表于 2019-06-24 11:14:49 回复(0)

字节跳动内推请找我

时间复杂度为o(n)，空间复杂度为o(1)
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null) return null;
        ListNode head0=new ListNode(0);
        head0.next=head;
        ListNode prev=head0;
        ListNode flag=head0;
        while(head != null)
        {
            if(head.val<x)
            {
                if(head==prev.next)
                {
                    prev=prev.next;
                    head=head.next;
                    flag=flag.next;
                }
                else 
                {
                    flag.next=head.next;
                    ListNode tmp=prev.next;
                    prev.next=head;
                    head.next=tmp;
                    
                    prev=prev.next;
                    head=flag.next;
                }
            }
            else {
                head=head.next;
                flag=flag.next;
            }
        }
        return head0.next;
    }
}

发表于 2019-06-02 14:52:51 回复(0)

超级无敌懒

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *less = new ListNode(0);
        ListNode *greater = new ListNode(1);
        
        ListNode *iter = head;
        ListNode *pLess = less, *pGreater = greater;
        while (iter != NULL)
        {
            if (iter->val < x)
            {
                pLess->next = iter;
                pLess = pLess->next;
            }
            
            if (iter->val >= x)
            {
                pGreater->next = iter;
                pGreater = pGreater->next;
            }
            iter = iter->next;
        }
        
        pGreater->next = NULL;
        pLess->next = greater->next;
        
        ListNode *re = less->next;
        
        delete less;
        delete greater;
        
        return re;
    }
};

发表于 2018-05-22 22:23:10 回复(0)

明霁*天明

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head==NULL)
            return NULL;
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* pre=dummy;
        ListNode* last=dummy;
        while(pre->next!=NULL)
            {
              if(pre->next->val>=x)
              {
                break;
              }
              pre=pre->next;
              last=last->next;
            }
        while(last->next!=NULL)
        {
            
            if(last->next->val<x)
            {
                ListNode* tem=last->next->next;
                last->next->next=pre->next;
                pre->next=last->next;
                last->next=tem;
                pre=pre->next;
                continue;
            }
            last=last->next;
        }
        return dummy->next;
    }
};

发表于 2017-11-22 14:20:34 回复(0)

root1024

思想不太一样

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null){
            return null;
        }
        //找到第一个>=x的节点firstHigh，以后<x的节点就顺序插入firstHigh前
        //考虑到有可能是head，所有准备个preHead节点
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        ListNode firstHigh = head,preHigh = preHead,node=head,preNode=preHead;
        while(node!=null){
            if(node.val>=x){
                firstHigh = node;
                preNode = node;
                node = node.next;
                break;
            }
            preNode = preHigh = node;
            node = node.next;
        }
        while(node!=null){
            if(node.val<x){
                preNode.next = node.next;
                node.next = firstHigh;
                preHigh.next = node;
                preHigh = node;
                node = preNode;
            }
            preNode = node;
            node = node.next;
        }
        return preHead.next;
    }
}

编辑于 2017-10-08 15:52:49 回复(0)

C/C++

nbgao

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        if(head == NULL)
        	return NULL;
        ListNode *L1 = new ListNode(0);
        ListNode *L2 = new ListNode(0);
        ListNode *p1 = L1;
        ListNode *p2 = L2;
        ListNode *p = head;
        while(p != NULL)
        {
        	if(p->val < x)
        	{
        		p1->next = p;
        		p1 = p1->next;
			}else{
				p2->next = p;
				p2 = p2->next;
			}
			p = p->next;
		}
		p2->next = NULL;
		p1->next = L2->next;
		return L1->next;
    }
};

发表于 2017-08-23 00:44:11 回复(0)

LinuX18

class Solution {
public:
    // 双指针
    ListNode *partition(ListNode *head, int x) 
    {
       ListNode *fake1 = new ListNode(0);
       ListNode *fake2 = new ListNode(0);
       ListNode *p1 = fake1,*p2=fake2;
       while(head)
       {
           if(head->val < x)
           {
               p1->next = head;
               p1 = p1->next;
           }
           else
           {
               p2->next = head;
               p2 = p2->next;
           }
           head = head->next;
       }
       p2->next = nullptr;
       p1->next = fake2->next;
       return fake1->next;
    }
};

发表于 2017-07-10 21:21:50 回复(0)

努力编程

你们这个破网站究竟咋滴了，我编译了好多个不是超时就是内存不够，在别的刷题网站上提交就没事

发表于 2017-06-17 20:21:31 回复(1)

元气の悟空

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        vector<int> d1,d2;
        int i;
        ListNode *p;
        for(p=head;p;p=p->next)
            if(p->val<x) d1.push_back(p->val);
            else d2.push_back(p->val);
        for(p=head,i=0;i<d1.size();p->val=d1[i],i++,p=p->next);
        for(i=0;i<d2.size();p->val=d2[i],i++,p=p->next);
        return head;
    }
};

发表于 2016-08-14 20:34:40 回复(0)

JacobGo！

题意：给定一个单链表和一个x，把链表中小于x的放到前面，大于等于x的放到后面，每部分元素的原始相对位置不变。

思路：新建两个节点preHead1与preHead2，分别为指向两个链表的头结点。

把节点值小于x的节点链接到链表1上，节点值大等于x的节点链接到链表2上。

最后把两个链表相连即可

public ListNode partition(ListNode head, int x) {
		//preHead1与preHead2分别为两个链表头结点的前移节点（一个链表的节点值小于x，另一个大于等于x）
		ListNode preHead1 = new ListNode(0), preHead2 = new ListNode(0);
		ListNode cur1 = preHead1, cur2 = preHead2;
		while (head != null) {
			if (head.val < x) {
				cur1.next = head;
				cur1 = cur1.next;
			} else {
				cur2.next = head;
				cur2 = cur2.next;
			}
			head = head.next;
		}
		cur1.next = preHead2.next;
		cur2.next = null;
		return preHead1.next;

	}

发表于 2017-08-17 12:17:58 回复(4)

LeBronWitness

O(n)复杂度，O(1)空间

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null) return head;
        ListNode dummy=new ListNode(0),p=dummy;
        dummy.next=head;
        while(p.next!=null&&p.next.val<x) p=p.next;
        ListNode q = p,pre=p;
        while(q.next!=null) {
            pre=q;q=q.next;
            if(q.val<x) {
                pre.next=q.next;
                q.next=p.next;
                p.next=q;
                p=q;
            }
        }
        return dummy.next;
    }
}

发表于 2019-05-04 19:17:09 回复(0)

提交观点

问题信息

链表双指针

难度：

152条回答 206收藏 21210浏览

通过挑战的用户

洞洞鞋小公主

2023-03-13 19:47:59
牛客20133...

2023-03-09 21:37:38
月澈

2023-03-09 07:40:50
K乀

2023-02-27 21:37:52
GeekExp...

2023-02-16 13:17:11