143. 重排链表

题目链接：143. 重排链表

题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

核心思考：利用栈结构逆序连接

链表不支持随机访问，无法直接获取尾部节点。为了实现首尾交替的重排，我们可以利用栈（Stack）后进先出（LIFO）的特性。

1. 第一次遍历：将链表的所有节点按顺序压入栈中。这使得我们可以通过不断弹栈（pop）的方式，逆序获取链表的尾部节点。
2. 第二次遍历与重组：使用指针 p 从头节点开始遍历。每次循环提取当前节点的下一个节点 next_node，并从栈顶弹出一个尾部节点 last_node。
3. 把弹出的 last_node 插入到 p 和 next_node 之间。
4. 指针 p 随后移动到 next_node，为下一组交替插入做准备。

细节：重组的终止条件

链表重排最关键的地方在于判断何时停止拼装，避免形成环路。这取决于链表节点总数的奇偶性：

• 当节点总数为偶数时：前后两个方向的指针最终会紧挨在一起。此时栈顶弹出的节点 last_node 刚好等于原链表中 p 的下一个节点 next_node。
• 当节点总数为奇数时：前后两个方向的指针最终会指向同一个中间节点。即栈顶弹出的 last_node 与当前的 p 是同一个节点。这也意味着此时 last_node.next == next_node。

当满足以上任意一种情况（last_node == next_node or last_node.next == next_node）时，说明首尾交替已经触达到链表的中心区域。此时必须断开循环，并将 last_node.next 显式置为 None，以封闭链表尾部，防止在此处继续循环引用从而产生死循环。

解题思路 (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        stack = []
        p = head
        while p is not None:
            stack.append(p)
            p = p.next
        
        p = head
        while p is not None:
            last_node = stack.pop()
            next_node = p.next
            if last_node == next_node or last_node.next == next_node:
                last_node.next = None
                break
            p.next = last_node
            last_node.next = next_node
            p = next_node

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表的长度。需要遍历链表两次，一次压栈，一次重组。
• 空间复杂度：$O(N)$。使用了额外的数组（栈）结构存储所有节点引用。