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

news/2024/11/14 0:09:44/

目录链接:

力扣编程题-解法汇总_分享+记录-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;如下&…