经典OJ题:重排链表

news/2024/7/5 5:31:47

题目:

给定一个链表,在进行重排前:

进行重排链表后:

 

如上图所示,所谓的重拍链表,就是将第一个节点连接第倒数第一个节点,第二个节点连接倒数第二个节点,以此类推,最后在连接起来。


题源:143. 重排链表 - 力扣(LeetCode) 

思路分析:

方法一:

设置一个新的链表,在设置两个指针分别指向新链表和原链表,指向原链表的指针进行遍历,遍历到需要的节点后进行尾插操作,插入新链表中,最后返回新链表。

方法二:

对于方法二,需要三种操作,寻找中间节点、链表反转、链表合并连接。

寻找中间节点,找到链表的中间部分,使用快慢指针。

 

链表的反转,经过多次的实验和画图,我们知道链表可以分为两种,分别是偶数节点个数的链表,另一个是奇数节点个数的链表,因此二者的中间节点也不一样。

而又通过链表的合并操作,我们得知,在这一步操作中,如果不把链表拆分成两条链表,那么之后的合并链表将会变得十分的艰难。

 

合并链表操作:

 

如图所示,l1_tamp 和 l2_tamp作为临时变量,进行存储 l1 和 l2 的下一个节点

而l1指向l2进行拼接后,l1需要到下一个节点的位置被l2连接

图例: 

 

完整代码:

 


操作参考: 

单链表经典OJ题:找出链表的中间节点-CSDN博客 

单链表经典OJ题:合并有序链表-CSDN博客 

单链表经典OJ题:反转链表-CSDN博客 


http://lihuaxi.xjx100.cn/news/1781507.html

相关文章

JAVA基础4:数据输入

1.Scanner使用的基本步骤 ①导包 import java.util.Scanner; 导包的动作必须出现在类定义的上边。 ②创建对象 Scanner sc new Scanner(System.in); 上面这个格式里面,只有sc是变量名,可以变,其他的都不允许变。 ③接收数据 int i sc.next…

Android修行手册 - 可变参数中星号什么作用(冷知识)

点击跳转>Unity3D特效百例点击跳转>案例项目实战源码点击跳转>游戏脚本-辅助自动化点击跳转>Android控件全解手册点击跳转>Scratch编程案例点击跳转>软考全系列 👉关于作者 专注于Android/Unity和各种游戏开发技巧,以及各种资源分享&…

【Git】的分支与版本

前言 Git 的分支是指将代码库从某一个特定的提交记录开始的一个独立的开发线,也可以理解为是一种代码开发的并行方式。分支在 Git 中的使用非常广泛,它可以让多人在同一个代码库中并行开发,同时也能够很方便地进行代码版本控制和管理。 Git …

Leetcode100120. 找出强数对的最大异或值 I

Every day a Leetcode 题目来源:100120. 找出强数对的最大异或值 I 解法1:模拟 枚举 2 遍数组 nums 的元素,更新最大异或值。 代码: /** lc appleetcode.cn id100120 langcpp** [100120] 找出强数对的最大异或值 I*/// lc c…

高二英语上

unit 1 1.yarn三种意思 1.码; 2.庭院,天井; 3.花园;down**down 在这里是介词,也可以作副词,与 down 相对的是 up。请比较下列两句: 1.Look! Hes driving down the street . 2.Look! Hes driving up the street .这两…

Java Web——TomcatWeb服务器

目录 1. 服务器概述 1.1. 服务器硬件 1.2. 服务器软件 2. Web服务器 2.1. Tomcat服务器 2.2. 简单的Web服务器使用 1. 服务器概述 服务器指的是网络环境下为客户机提供某种服务的专用计算机,服务器安装有网络操作系统和各种服务器的应用系统服务器的具有高速…

systemd-timesyncd

介绍 systemd-timesyncd 是一个用于跨网络同步系统时钟的守护服务。它实现了一个 SNTP 客户端。与NTP的复杂实现相比,这个服务简单的多,它只专注于从远程服务器查询然后同步到本地时钟。除非你打算为客户端提供 NTP 服务器或者连接本地硬件时钟&#xff…

Leetcode—107.二叉树的层序遍历II【中等】

2023每日刷题(二十七) Leetcode—107.二叉树的层序遍历II 实现代码 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullpt…