难度: Medium
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4] 输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3]
提示：
[1, 5 * 104]1 <= node.val <= 1000注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/
运行时间: 33 ms
内存: 21.4 MB
# 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: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
def reverList(head):
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
pre = ListNode()
pre.next = head
slow = fast = pre
while fast and fast.next:
slow = slow.next
fast = fast.next.next
half = slow.next
slow.next = None
revHalf = reverList(half)
cur = pre.next
while slow and revHalf:
tmp = cur.next
cur.next = revHalf
cur = cur.next
revHalf = revHalf.next
cur.next = tmp
cur = cur.next
题解分为三个主要部分：1. 使用快慢指针找到链表的中间节点，从而将链表分为前半部和后半部。2. 反转链表的后半部分。3. 将反转后的后半部分交替插入前半部分中，从而达到题目要求的重排。快慢指针技巧用于高效找到链表中点，链表反转则是常规操作，最后的合并需要细心操作节点指针以避免丢失或混乱。
时间复杂度: O(n)
空间复杂度: O(1)
# 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: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
def reverList(head):
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
pre = ListNode()
pre.next = head
slow = fast = pre
while fast and fast.next:
slow = slow.next
fast = fast.next.next
half = slow.next
slow.next = None
revHalf = reverList(half)
cur = pre.next
while cur and revHalf:
tmp = cur.next
cur.next = revHalf
cur = cur.next
revHalf = revHalf.next
cur.next = tmp
cur = cur.next
# 列表被改变到指定的重新排序状态
在找到链表中点后，将链表从中间断开成两个部分是必要的，因为重排链表的目的是将后半部分的元素逆序后，依次插入到前半部分的元素之间。如果不将链表分成两部分，就无法单独操作后半部分进行反转，也就无法按照题目要求完成链表的重排操作。断开后，可以独立处理后半部分，进行反转，然后再将反转后的部分逐一插入到前半部分中。
在反转链表的过程中，设定`pre`为`None`是用来初始化反转链表的尾部节点。在反转过程中，每个节点的`next`指针需要指向前一个节点，因此第一个节点反转后，它的`next`应该指向`None`表示链表的末尾。`pre`作为一个临时变量，用来存储已经反转部分的最后一个节点，随着遍历逐步向前移动，帮助完成整个链表的反转。
为了确保在反转后半部分的链表时不丢失原链表的数据，算法中采用了临时变量`tmp`来保存当前节点的下一个节点（`cur.next`）。这个操作保证了在修改当前节点的`next`指针指向前一节点（完成反转的一部分）时，不会丢失对后续链表部分的引用。每次迭代中，都先将`cur.next`存储在`tmp`中，然后更新`cur.next`，最后将`cur`更新为`tmp`。这样，即使反转了链接方向，每个节点的原始连接也不会丢失，从而保持了链表数据的完整性。