- 标签:栈、递归、链表、双指针
- 难度:中等
给定一个单链表 L
的头节点 head
,单链表 L
表示为:$L_0$ ->
要求:将单链表 L
重新排列为:$L_0$ ->
注意:需要将实际节点进行交换。
链表不能像数组那样直接进行随机访问。所以我们可以先将链表转为线性表。然后直接按照提要要求的排列顺序访问对应数据元素,重新建立链表。
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return
vec = []
node = head
while node:
vec.append(node)
node = node.next
left, right = 0, len(vec) - 1
while left < right:
vec[left].next = vec[right]
left += 1
if left == right:
break
vec[right].next = vec[left]
right -= 1
vec[left].next = None