143. 重排链表

题目

给定一个单链表 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 * 10^4]
• 1 <= node.val <= 1000

解答

思路

以 [1, 2, 3, 4, 5] 变成 [1, 5, 2, 4, 3] 为例：

• 首先将 [3, 4, 5] 反转成 [5, 4, 3]
• 然后将 [1, 2] 和 [5, 4, 3] 拼接起来
• 直到 head2 指向 3 停止，也就是 head2.next = None 时

由于寻找中间节点需要 $O(n)$ 的时间，反转链表也需要 $O(n)$ 的时间，最后合并也需要 $O(n)$ 的时间。因此：

• 时间复杂度为 $O(2n)$
• 空间复杂度为 $O(1)$

代码

Python 代码

class Solution:
    # 876. 链表的中间结点
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

    # 206. 反转链表
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        return pre
    
    def reorderList(self, head: Optional[ListNode]) -> None:
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)

        while head2.next: # head 此时仍有所指，不为空
            nxt = head.next
            nxt2 = head2.next

            head.next = head2
            head2.next = nxt

            head = nxt
            head2 = nxt2