143_重排链表

类型：链表

重排链表 💛

https://leetcode-cn.com/problems/reorder-list/

❓ 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

💡 线性表

因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。

容易想到的方法是，我们利用线性表存储该链表，利用线性表可以下标直接访问的特点，按顺序访问指定元素，重建该链表即可。

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        vec = list()
        node = head
        while node:
            vec.append(node)
            node = node.next

        i, j = 0, len(vec) - 1
        while i < j:
            vec[i].next = vec[j]
            i += 1
            if i == j:
                break
            vec[j].next = vec[i]
            j -= 1

        vec[i].next = None

时间复杂度：O(n)，空间复杂度：O(n)

💡 寻找链表中点 + 链表逆序 + 合并链表

我们注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。

这样我们的任务即可划分为三步：

找到原链表的中点（参考「876. 链表的中间结点」）。我们可以使用快慢指针来O(N) 地找到链表的中间节点。
将原链表的右半端反转（参考「206. 反转链表」）。我们可以使用迭代法实现链表的反转。
将原链表的两端合并。因为两链表长度相差不超过 1，因此直接合并即可。

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        mid = self.middleNode(head)
        l1 = head
        l2 = mid.next
        mid.next = None
        l2 = self.reverseList(l2)
        self.mergeList(l1, l2)

    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            nextTemp = curr.next
            curr.next = prev
            prev = curr
            curr = nextTemp
        return prev

    def mergeList(self, l1: ListNode, l2: ListNode):
        while l1 and l2:
            l1_tmp = l1.next
            l2_tmp = l2.next

            l1.next = l2
            l1 = l1_tmp

            l2.next = l1
            l2 = l2_tmp

时间复杂度：O(n)，空间复杂度：O(1)