​LeetCode解法汇总143. 重排链表

news/2024/4/15 8:13:03

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:
143. 重排链表


描述:

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]
输出:[1,4,2,3]

示例 2:

输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]

提示:

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

解题思路:

/**

* 143. 重排链表

* 解题思路:

* 链表长度5*10^4,所以递归的方式不可取。

* 这题如果使用额外的数据结构,比如把链接转换成数组,那么问题就会变得很简单,所以暂且把目标设置为不使用额外空间。

* 使用快慢指针的策略,快指针走两个节点,慢指针走一个节点,这样,我们可以找到中间节点。

* 然后使用头插法,把中间节点后面的所有节点翻转,生成翻转链表foot

* 重新遍历head链表,直到遍历到middle节点。每次遍历,head和foot链表各取一个

*

*/

代码:

class Solution143
{
public:void reorderList(ListNode *head){ListNode *quick = head;ListNode *slow = head;while (true){quick = quick->next;if (quick == nullptr){break;}slow = slow->next;quick = quick->next;if (quick == nullptr){break;}}// 第二块逻辑ListNode *middle = slow;ListNode *foot = nullptr;ListNode *current = middle;while (current != nullptr){ListNode *local = current;current = current->next;local->next = foot;foot = local;}// 第三块逻辑ListNode *header = head->next;ListNode *footer = foot;current = head;while (current != middle){current->next = footer;  // 1->5footer = footer->next;   // footer=>4current = current->next; // current=>5if (current == middle){break;}current->next = header;  // 5->2header = header->next;   // header=>3current = current->next; // current=>2}cout << head->val << endl;}
};


http://www.ppmy.cn/news/995040.html

相关文章

思科认证 | CCIE考过了,证书编号怎么查?

考CCIE证书是一个很辛苦的过程&#xff0c;你努力考证的最终目的就是为了拿证&#xff0c;有了CCIE证书你才能证明你自己的技术能力。 那么如何查询CCIE证书呢&#xff1f;看这里。 01 如何查询CCIE证书 1. Cisco官方认证查询系统 Cisco官方网站提供了一个在线认证查询系统&a…

Java版本spring cloud + spring boot企业电子招投标系统源代码

&#xfeff;项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&…

PyKDL 求解Panda机械臂逆运动学

1.python3.6安装PyKDL pip install PyKDL不行,import的时候失败了,只能源码编译 GitHub - orocos/orocos_kinematics_dynamics: Orocos Kinematics and Dynamics C library 具体安装可以参考:ROS编译PyKDL python3_RuiH.AI的博客-CSDN博客 其中pybind11这个下载的时候比较慢…

分享一些精选的开源框架与代码!

今天主要是收集并精选了一些自己所了解和学习过的优秀的嵌入式开源框架代码和项目&#xff0c;不太了解的就不推荐给大家了&#xff0c;因为开源的东西实在是太多了&#xff0c;鱼龙混杂&#xff0c;所以取其精华去其糟粕是迫在眉睫的大事~ 当然也不要总是沉浸在开源的东西之中…

#P0997. [NOIP2006普及组] 数列

题目描述 给定一个正整数k(3≤k≤15)k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列&#xff0c;例如&#xff0c;当k3k3时&#xff0c;这个序列是&#xff1a; 1,3,4,9,10,12,13,…1,3,4,9,10,12,13,… &#xff08;该序列实际上就是&…

SqlServer 批量删除表

SqlServer 批量删除表 直接上SQL脚本吧 SELECT row_number()over(order by Name) as FID,Name into #temp FROM SysObjects Where XTypeU --类型&#xff0c;U为实体表 and name like TMP% --表名过滤&#xff08;自定义就好&#xff09; ORDER BY Namedeclare count int 0…

什么是MES,什么是WMS,MES与WMS有什么区别?

什么是MES&#xff1f;什么是WMS&#xff1f;以及MES&#xff08;制造执行系统&#xff09;与WMS&#xff08;仓库管理系统&#xff09;的区别&#xff0c;下面分为三块跟大家详细讲解。 一、什么是MES&#xff1f; 1、概念&#xff1a; MES&#xff08;英文全称&#xff1a…

今天是啥时候?

描述 定义一个结构体变量&#xff08;包括年、月、日&#xff09;。计算该日在本年中是第几天&#xff0c;注意闰年问题。。 输入 年月日 输出 当年第几天 输入样例 1 2020 2 28 输出样例 1 59 输入样例 2 2022 9 5 输出样例 2 248 代码一&#xff08;如下&…

TWILIGHT靶场详解

TWILIGHT靶场详解 下载地址&#xff1a;https://download.vulnhub.com/sunset/twilight.7z 这是一个比较简单的靶场&#xff0c;拿到IP后我们扫描发现开启了超级多的端口 其实这些端口一点用都没有&#xff0c;在我的方法中 但是也有不同的方法可以拿权限&#xff0c;就需要…

复习第二章之Redis

一、什么是Redis Redis 本质上是一个 Key-Value 类型的内存数据库&#xff0c;很像 memcached&#xff0c;整个 数据库统统加载在内存当中进行操作&#xff0c;定期通过异步操作把数据库数据 flush 到硬盘 上进行保存。因为是纯内存操作&#xff0c;Redis 的性能非常出色&…

js中的dom

HTML DOM对象(Document Object Model)&#xff1a;是一种文档对象模型&#xff0c;从js的角度&#xff0c;认为网页中的每一个标签都是一个独立的对象&#xff0c;这一类对象称为dom对象&#xff0c;以面向对象的思想来操作网页内容 获取dom对象 一般有四种方式进行获取&…

【redis】redis部署1主2从3哨兵demo搭建示例

redis版本为7&#xff0c;搭建的架构为1主2从3哨兵的架构。本文是对搭建的过程做一个回忆&#xff0c;过程可能遗漏了某些步骤&#xff0c;见谅。 首先&#xff0c;需要有一个已经安装了的redis。我们从redis源码目录中&#xff0c;找到一个redis.conf文件&#xff0c;这个文件…

步入智能自动化:RPA迁移过程中的实践与考量

2023年对于自动化行业来说&#xff0c;是充满变革的一年。随着新一代智能自动化平台为用户带来更为简洁的体验&#xff0c;以及许多顶尖的RPA供应商大幅度提升价格和许可费用&#xff0c;众多企业开始考虑或已经开始将他们的RPA资源从传统工具转向新的智能自动化平台。 当我们说…

linux判断端口是否占用(好用)

netstat 一般的话使用 netstat -tunlp | grep xxx参数作用-t指明显示TCP端口-u指明显示UDP端口-l仅显示监听套接字(所谓套接字就是使应用程序能够读写与收发通讯协议(protocol)与资料的程序)-p显示进程标识符和程序名称&#xff0c;每一个套接字/端口都属于一个程序。-n不进行…

【SpringBoot】| SpringBoot 和 web组件

目录 一&#xff1a;SpringBoot 和 web组件 1. SpringBoot中使用拦截器&#xff08;重点&#xff09; 2. SpringBoot中使用Servlet 3. SpringBoot中使用过滤器&#xff08;重点&#xff09; 4. 字符集过滤器的应用 一&#xff1a;SpringBoot 和 web组件 1. SpringBoot中使…

最适合新手的Java项目/SpringBoot+SSM项目《苍穹外卖》/项目实战、笔记(超详细、新手)[持续更新……]

小知识 软件设计中提到的UI设计中的UI是什么意思&#xff1f; 在软件设计中&#xff0c;UI设计中的UI是User Interface的简称&#xff0c;即用户界面。UI设计是指对软件的人机交互、操作逻辑、界面美观的整体设计。好的UI设计可以让软件变得有个性有品位&#xff0c;同时让操作…

linux服务器anaconda环境配置

如何在Linux系统服务器中安装anaconda3 下载anaconda3的压缩文件&#xff0c;这里的版本可以自己选择&#xff0c;文件下载所在的目录是当前终端所在的目录 wget https://repo.anaconda.com/archive/Anaconda3-2021.05-Linux-x86_64.sh2。解压下载的压缩包 bash Anaconda3-2…

压缩包工具类

压缩包工具类&#xff08;下载&#xff09; import com.enlistboot.common.core.FileResult; import org.springframework.http.HttpHeaders; import org.springframework.util.ObjectUtils;import javax.servlet.http.HttpServletResponse; import java.io.*; import java.net…

揭秘!头条百科词条创建全过程及技巧解析

随着互联网时代的到来&#xff0c;人们获取信息的方式越来越便捷。作为国内领先的信息平台&#xff0c;头条百科成为了很多人查阅知识的首选。然而&#xff0c;如何在头条上创建百科词条&#xff0c;让更多人了解和熟知自己呢&#xff1f;本文伯乐网络传媒将为您揭开这个谜团&a…

OpenLayers实战,OpenLayers使用wind-layer插件实现风场动态效果

专栏目录: OpenLayers入门教程汇总目录 前言 本章讲解如何使用OpenLayers的气象风场插件wind-layer实现气象风场动态效果,该插件除了可用于OpenLayers之外,还可用于mapgl、leaflet和cesuim等二维/三维地图引擎,还是很强大的,废话少谈,让我们立刻开始实现吧。 二、依赖和…
最新文章