我要招人

去企业版

首页 > 试题广场 >

划分链表

[编程题]划分链表

热度指数：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，点此查看相关信息

算法知识视频讲解

堆栈哲学

发表于 2021-07-11 21:55:10

精华题解题意分析：一个原始链表，一个整数x,对该链表进行如下规则的操作。以x为分界，将链表划分为两部分。val<x和val>=x 两个部分之内的节点之间要保持的原始相对顺序解法一：模拟（推荐）思路步骤：由于要将链表按照规则分割为两部分，可以考虑维护两个链表small和large 展开全文

漫漫云天自翱翔

发表于 2021-07-16 22:51:23

精华题解题解一：创建两个节点分别指向大于x和小于x图示：复杂度分析：时间复杂度：O(n) 空间复杂度：O(1)实现如下： class Solution { public: /** * * @param head ListNode类 * @p 展开全文

认认真真coding

发表于 2021-07-16 11:37:17

精华题解题目描述给出一个链表和一个值，以x为参照将链表划分成两部分，使所有小于x的节点都位于大于或等于x的节点之前。两个部分之内的节点之间要保持的原始相对顺序。例如：给出 1→4→3→2→5→2和x=3,返回 1→2→2→4→3→5. 方法一：暴力求解求解思路对于题目所要求，将小于x的节点放到大于等于x 展开全文

华科不平凡

发表于 2020-09-24 15:32:19

题目理解起来有点费劲：使所有小于x的节点都位于大于或等于x的节点之前，意思是只需要小于等于x的节点位于链表前面即可，不要求小于在前，等于在中，大于在后。采用双哑节点+双指针，先构建中间链表，然后将两个链表合并：哑节点指向两个中间链表的头部指针指向两个中间链表的尾部代码如下： // // 展开全文

程序员学长

发表于 2021-10-31 22:44:36

划分链表问题描述面试题 02.04. 分割链表给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。示例：输入：head = [1,4,3,2,5,2 展开全文

20152021

发表于 2020-12-10 11:09:25

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @ 展开全文

总之就是非常可爱

发表于 2022-02-22 19:53:58

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class 展开全文

数据结构和算法

发表于 2021-08-03 15:42:56

四指针解决在算法中双指针我们经常听过，但四指针还是比较少的，四指针顾名思义就是使用4个指针来解决。这题是让把节点值小于x的节点都放到前面，最简单的一种解决方式就是把原链表的节点分隔为两个链表，其中一个链表节点的值都是小于x的，另一个链表节点的值都是大于或等于x的，最后再把这两个链表合并即可。这里展开全文

空中转体一周半

发表于 2022-03-11 12:09:52

思路：把链表分成两个部分，左边是比目标x小的，断链即可，最后再连接起来。 public class Solution { public ListNode partition (ListNode head, int x) { ListNode left = new List 展开全文

太阳hxy

发表于 2023-07-13 23:51:22

划分链表方法一：创建两个表之后进行连接思路： 1.创建两个表的虚的头节点 2.遍历原先的表，将大于等于x的节点找出来连在存大的节点的表中，将小于x的节点找出来连在用于存小于x的节点的表中 3.再将两个表进行连接代码： import java.util.*; /* * public 展开全文

jing_zhong

发表于 2021-09-13 18:01:28

题目描述:给出一个长度为 nn 的单链表和一个值 xx ，单链表的每一个值为 list[i]list[i]，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。示例1 &nb 展开全文

小陆要懂云

发表于 2021-09-03 10:50:17

直观来说我们只需维护两个链表small 和large 即可： small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后，将small 链表尾节点指向large 链表的头节点，完成两个链表的合并。为了实现上述思路，我们设smallHead 和展开全文

一叶舟troy

发表于 2021-07-28 14:17:43

搜索微信公共号：offer 多多 class Solution3 { public: /** * * @param head ListNode类 * @param x int整型 * @return ListNode类 */ 展开全文

问题信息

链表双指针

难度：

152条回答 206收藏 21205浏览

通过挑战的用户

洞洞鞋小公主

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

划分链表

输入

输出

输入

输出

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

问题信息

热门推荐

通过挑战的用户

相关试题