【leetcode——重排链表】-ag九游会j9官方网站

【leetcode——重排链表】

2023-05-24

33 浏览

江海入海，知识涌动，这是我参与江海计划的第15篇。

@[toc](文章目录)

一、重排链表

对于这道题，有两种思路：

## 思路1.

**1.使用一个线性表，存储链表中的每个节点，然后按照题目的条件，来链接线性表的各个节点即可。**

**使用左下标和右下标来定位线性表中的节点。**

**1.先存储链表中的节点数据到线性表**

**2.循环条件是front < tail**

**时间复杂度为o(n)，空间复杂度为o(n)**

思路2.

**（1）找到链表的中间节点

（2）将链表中间节点开始之后的链表逆置

（3）将两个链表重新合并**

（1）找链表的中间节点可以使用快慢指针来求出。

快指针一次走两步，慢指针一次走一步。

（2）链表逆置，有两种方法，一种方法是使用三指针，一种方法是使用头插。

三指针法：

（3）合并两个链表，合并链表，从两个链表的头节点开始链接。

**时间复杂度o(n)，空间复杂度o(1)**

总结

**两种方法各有好处，法1空间复杂度大，但是易于理解。

法2相对更难理解，但是空间复杂度小。**

请后发表内容