[python 刷题] 143 Reorder List

[python 刷题] 143 Reorder List

题目：

You are given the head of a singly linked-list. The list can be represented as:

$L_0\to L_1\to \dots \to L_{n-1}\to L_n$

Reorder the list to be on the following form:

$L0\to Ln\to L1\to Ln-1\to L2\to Ln-2\to \dots$

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

这道题虽然说不允许修改链表结点上的值，但是改了也能过……那样的解法就是将所有的值保存在一个数组里，然后遍历整个数组，通过判断数组当前所在的结点去修改值。

当然，因为这道题已经明确说了，不允许修改链表结点上的值， 所以这种是能过但是面试情况下是不行的情况 🙅

正确的做法是找到链表的一半，翻转后半段，再一个个交替串联，所以这种情况下来说，[JavaScript 刷题] 链表 - 反转链表, leetcode 206 可以算是这道题的前置题。

这道题唯一需要注意一点的地方在于寻找的中点。

当链表长度为偶数时：

当链表长度为奇数时：

这个时候对链表进行反转并不会产生理想的效果，反而会让中点有两个头，产生这样的效果：

和

这样也就意味着会产生环形链表，所以正确的做法是找到中点前的结点 prev，在完成翻转后，将 prev 指向空，这样就有了两个不相关的链表，也就不会出现环形链表的情况

最终解法如下：

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

        def reverse(node):
            if not node or not node.next:
                return node

            new_head = reverse(node.next)
            node.next.next = node
            node.next = None

            return new_head

        l_reversed = reverse(l_slow.next)
        l_slow.next = None

        while l_reversed:
            temp1, temp2 = head.next, l_reversed.next
            head.next = l_reversed
            l_reversed.next = temp1
            head, l_reversed = temp1, temp2
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
27
28
29