0143：重排链表（★）

2015-05-23 约 334 字预计阅读 1 分钟次阅读

力扣第 143 题

题目

给定一个单链表 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

分析

先用快慢节点找到中点位置，截断为两部分
将后半部分链表反转后依次插入前半部分中即可
反转链表即是问题 0206

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        def reverse(head):
            tail = head
            while tail and tail.next:
                tmp = tail.next
                tail.next = tmp.next
                tmp.next = head
                head = tmp
            return head

        slow = fast = ListNode(next=head)
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        q = slow.next
        slow.next = None
        p, q = head, reverse(q)
        while q:
            tmp = p.next
            p.next = q
            q = q.next
            p.next.next = tmp
            p = tmp

63 ms

目录

0143：重排链表（★）

题目

分析

解答