143. 重排链表

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

L_0 → L_1 → … → L+{n-1} → L_n 

请将其重新排列后变为：

L_0 → L_n → L_1 → L_{n-1} → L_2 → 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^4]
• 1 <= node.val <= 1000

Python 解答：
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: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head.next:
            return
        adic = {}
        n = 0
        p = head
        while p:
            adic[n] = p
            n += 1
            p = p.next
        pre = None
        j = 0 
        while j < n//2:
            if pre:
                pre.next = adic[j]
            adic[j].next = adic[n-j-1]
            pre = adic[n-j-1]
            j += 1
        if n%2 == 1:
            pre.next = adic[n//2]
            adic[n//2].next = None
        else:
            pre.next = None

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

2.链表