首页 > 试题广场 >

重排链表

[编程题]重排链表
  • 热度指数：129962 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
将给定的单链表：
重新排序为：
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 ，链表中每个节点的值满足

要求：空间复杂度 并在链表上进行操作而不新建链表，时间复杂度
进阶：空间复杂度 ， 时间复杂度
示例1

输入

{1,2,3,4}

输出

{1,4,2,3}

说明

给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1
示例2

输入

{1,2,3,4,5}

输出

{1,5,2,4,3}

说明

给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出
示例3

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 Maokt
发表于 2021-07-05 09:55:12
精华题解 算法思想一：数组 解题思路： 因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。 因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。 算法步骤： 1、初始化空数组res，遍历链表将 展开全文
去ta的博客 赞 (45) 回复(1) 收起
头像 NumPy
发表于 2021-07-09 21:53:46
精华题解 一、题目描述 NC2重排链表题目大意：将给定的单链表 a0 -> a1 -> ... -> an-1 -> an，重新排序为a0 -> an -> a1 -> an-1 -> ...注意审题：要求使用原地算法，即节点内部的值不允许改变，需要对实际的节点 展开全文
去ta的博客 赞 (20) 回复(2) 收起
头像 牛一霸
发表于 2021-07-03 19:06:10
精华题解 题目：重排链表 描述：将给定的单链表 L：L0→L1→…→Ln−1→Ln重新排序为：L0→Ln→L1→Ln−1→L2→Ln−2→…L_0→L_n要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。 示例1：输入：{1,2,3,4}，返回值：{1,4,2,3} 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Peterliang
发表于 2021-07-15 18:21:13
精华题解 题意分析 给出一个链表，需要我们对这个链表进行重新排列，交错取出原来的链表最前面没有被取过的和最后面没有被取过的结点，新的链表就是按照这个取出的顺序重新拼接而成的一个链表。 样例解释 思路分析 题目的意思是给我们一个链表的头结点，需要我们不能改变结点内部的值，只能改变结点的next指针。这样 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 leaves0924
发表于 2021-07-08 14:02:17
精华题解 题目描述 将给定的单链表L： L_0→L_1→…→L_{n-1}→L_n重新排序为：L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。示例1输入：{1,2,3,4}返回值：{1,4,2,3}说明：给定head链表1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 LaN666
发表于 2020-11-22 17:07:05
解法一 线性表 我们都知道链表的缺点是查询效率低，每一次都需要从头开始遍历。所以如果按照题目的要求组成新链表，要去得到最后一个节点，就得从头将链表遍历一次，这样反复操作，直到将原来的链表改变到题目要求的链表。这样很明显是非常耗时间的。、 由于有了上面的分析，直到了这一缺点，我们就可以想到与链表齐 展开全文
去ta的博客 赞 (51) 回复(1) 收起
头像 Foreordination
发表于 2021-09-06 17:40:22
1、双指针算法 import java.util.*; public class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) return 展开全文
去ta的博客 赞 (16) 回复(0) 收起
头像 夏发财
发表于 2021-09-25 16:59:00
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * 展开全文
去ta的博客 赞 (13) 回复(1) 收起
头像 巨人的肩膀
发表于 2019-08-24 10:24:43
class Solution { public: void reorderList(ListNode *head) { if (head == NULL || head->next == NULL || head->next->next == NULL) 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 程序员学长
发表于 2021-11-02 14:14:43
更多题解，请关注公众号：程序员学长，让你进大厂不走弯路 重排链表 问题描述 LeetCode 143. 重排链表 给定一个单链表 L 的头节点head ，单链表 L 表示为：L0 -> L1 -> ... -> Ln-1 -> Ln，将其重新排列后变成 L0 -> Ln 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 小陆要懂云
发表于 2021-08-13 20:30:02
if (head == NULL || head->next == NULL || head->next->next == NULL) return; vector<ListNode *> v; while(hea 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 独饮心上秋要实习
发表于 2022-01-26 15:10:37
* struct ListNode { * int val; * struct ListNode *next; * }; * * C语言声明定义全局变量请加上static，防止重复定义 */ /** * * @param head ListNode类 * @return v 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 idealthm
发表于 2021-10-11 21:46:28
思路其实挺简单的. 我们需要将头结点率先链接至尾节点.并且为了可持续性地将tail = tail -> pre. 在O(1)空间的情况下,使用递归是最好的选择. 使用一个全局变量保存为当前链的起始头部.而递归则是最先处理最尾部的节点 //这里我们只考虑最后一个节点5,是如何被放入头结点的. / 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 LifelongCode
发表于 2021-01-06 22:35:32
- 解法1：划分+逆序+拼接；- 解法2：线性表； 解法1：划分+逆序+拼接 eg： 1->2->3->4->5->6 第一步：将链表分为两个链表 ​ 1->2->3 4->5->6 第二步：将第二个链表逆序 ​ 1->2->3 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 勤奋是成功者的通行证
发表于 2021-12-21 23:54:56
先用快慢指针找到中点，然后将后半部分进行翻转，最后在对这两个链表进行合并。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * Lis 展开全文
去ta的博客 赞 (3) 回复(0) 收起

问题信息

链表
难度：
383条回答 43613浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号