0143. 重排链表 #
- 标签:栈、递归、链表、双指针
- 难度:中等
题目大意 #
描述:给定一个单链表 L
的头节点 head
,单链表 L
表示为:$L_0$ -> $L_1$ -> $L_2$ -> … -> $L_{n-1}$ -> $L_n$。
要求:将单链表 L
重新排列为:$L_0$ -> $L_n$ -> $L_1$ -> $L_{n-1}$ -> $L_2$ -> $L_{n-2}$ -> $L_3$ -> $L_{n-3}$ -> …。
说明:
- 需要将实际节点进行交换。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:线性表 #
因为链表无法像数组那样直接进行随机访问。所以我们可以先将链表转为线性表,然后直接按照提要要求的排列顺序访问对应数据元素,重新建立链表。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。