重排链表

难度: Medium

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

L₀ → L₁ → … → L_{n - 1} → L_n

请将其重新排列后变为：

L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 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 * 10⁴]
1 <= node.val <= 1000

Submission

运行时间: 108 ms

内存: 23.1 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: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head is None:
            return head

        f = s = head
        while f and f.next:
            f = f.next.next
            s = s.next

        l1 = head
        l2 = s.next
        s.next = None

        def reverse(h):
            pre = None
            cur = h
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre

        l2 = reverse(l2)
        while l1 and l2:
            tmp = l1.next
            l1.next = l2
            l2 = l2.next
            l1.next.next = tmp
            l1 = l1.next.next

Explain

该题解的思路可以分为以下几个步骤： 1. 使用快慢指针找到链表的中点，将链表分为前后两个部分 l1 和 l2。 2. 反转后半部分链表 l2。 3. 将 l1 和反转后的 l2 依次连接，得到重排后的链表。

时间复杂度: 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: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head is None:
            return head
        
        # 使用快慢指针找到链表中点
        f = s = head
        while f and f.next:
            f = f.next.next
            s = s.next
        
        # 将链表分为前后两部分 l1 和 l2
        l1 = head
        l2 = s.next
        s.next = None
        
        # 反转链表 l2
        def reverse(h):
            pre = None
            cur = h
            while cur:
                tmp = cur.next
                cur.next = pre
                pre = cur
                cur = tmp
            return pre
        
        l2 = reverse(l2)
        
        # 合并 l1 和反转后的 l2
        while l1 and l2:
            tmp = l1.next
            l1.next = l2
            l2 = l2.next
            l1.next.next = tmp
            l1 = l1.next.next

Explore

当使用快慢指针方法确定链表中点时，快指针每次移动两步，慢指针每次移动一步。在链表长度为奇数时，快指针会在达到末尾的null节点停止（即快指针的next或next.next为null时）。此时慢指针正好位于中间节点。例如，在一个具有5个节点的链表中，当快指针到达末尾的null时，慢指针将位于第3个节点，正是中间的节点。这种方法确保了慢指针停在正中间的节点上，符合题目的要求。

在题解中，s指针在快慢指针的过程中最终指向前半部分链表的最后一个节点。因此，s.next自然指向后半部分链表的第一个节点，这就是新的链表l2的起点。从s开始反转会将前半部分的尾部也包括进来，这与题目要求重排链表而不是整体反转链表是不符的。因此，选择s.next作为起点是为了正确分离两个部分，仅对后半部分进行反转处理。

在合并链表的过程中，如果l1的长度大于l2的长度，会存在l1中还有剩余节点而l2已经全部插入的情况。由于题解中的合并过程是交替进行的，当l2节点用尽时，l1中的剩余节点已经正确地位于链表的末尾，不需要额外的操作。合并操作自然终止在l2节点用尽时，剩余的l1节点保持其原有的顺序即可。

当处理非常长的链表时，递归反转确实可能因为深度过大导致栈溢出。可以使用非递归的方法来反转链表，这通常涉及使用迭代方式。在迭代方法中，我们使用两个指针，pre和cur，初始化pre为null，cur为链表的头节点。在迭代过程中，将cur的next指向pre，然后更新pre和cur的值，直到cur为null。这种方法不涉及递归调用，因此不会导致栈溢出，适合处理大型数据。