跳至主要內容

剑指 Offer II 026. 重排链表

ITCharge小于 1 分钟

剑指 Offer II 026. 重排链表open in new window

  • 标签:栈、递归、链表、双指针
  • 难度:中等

题目链接

题目大意

给定一个单链表 L 的头节点 head,单链表 L 表示为:L0L_0 -> L1L_1 -> L2L_2 -> ... -> Ln1L_{n-1} -> LnL_n

要求:将单链表 L 重新排列为:L0L_0 -> LnL_n -> L1L_1 -> Ln1L_{n-1} -> L2L_2 -> Ln2L_{n-2} -> L3L_3 -> Ln3L_{n-3} -> ...。

注意:需要将实际节点进行交换。

解题思路

链表不能像数组那样直接进行随机访问。所以我们可以先将链表转为线性表。然后直接按照提要要求的排列顺序访问对应数据元素,重新建立链表。

代码

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