题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/reorder-list/
给定一个单链表 L : L 0 → L 1 → . . . → L n − 1 → L n L: L_{0} \rightarrow L_{1} \rightarrow ... \rightarrow L_{n-1} \rightarrow L_{n} L:L0→L1→...→Ln−1→Ln 将其重新排列后变为： L 0 → L n → L 1 → L n − 1 → L 2 → L n − 2 → . . . L_{0} \rightarrow L_{n} \rightarrow L_{1} \rightarrow L_{n-1} \rightarrow L_{2} \rightarrow L_{n-2} \rightarrow ... L0→Ln→L1→Ln−1→L2→Ln−2→...
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.先看题目，题目中给出一个单链表，要求重新排列成新的链表。先看示例 2：
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.可以看出这里重新排列的要求是，链表首节点指向末尾节点，末尾节点紧接着指向第二个节点，第二个节点又指向倒数第二个节点交换 … 依次类推。其中这里需要注意的是：【不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。】
这里先说下链表，在链表中，每次需要取出某个数据时，都需要遍历链表，无法随意访问。
在这道题目当中，需要频繁取数据，直接使用链表会非常麻烦。
那么，这里我们可以考虑使用线性表存储题目给定的单链表，然后利用线性表可随意访问数据的特性，访问指定元素，交换节点，重建链表。
这里直接看具体的代码实现。
# 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: return # 线性表存储链表节点 lst = [] node = head while node: lst.append(node) node = node.next # 定义指针指向首尾，开始取节点重建链表 start = 0 end = len(lst) - 1 while start < end: # 重新排列 lst[start].next = lst[end] start += 1 if start == end: break lst[end].next = lst[start] end -= 1 lst[start].next = None时间复杂度： O ( N ) O(N) O(N)， N N N 表示链表的节点数。
空间复杂度： O ( N ) O(N) O(N)， N N N 表示链表的节点数，这里主要是线性表的使用空间。
结合前面的代码实现，再看示例 2，
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.我们可以发现，重新排列的结果，可以看成原链表从中间节点分成两部分，然后将右边部分逆序之后，两部分合并成新的链表。
就以上面示例 2 来说明，
给定链表 1->2->3->4->5此时从链表中间节点进行切分，
左边部分 1->2->3 右边部分 4->5将右边部分进行逆序，此时
左边部分 1->2->3 右边部分（逆序后） 5->4现在将两部分依次合并，
合并后 1->5->2->4->3这里就是这个方法的大致思路：
先找到原链表的中间节点，以此将原链表划分为左、右两部分（使用快慢指针）；然后将右边部分进行逆序（迭代+双指针）；最后将左边部分与逆序后的右边部分依次合并。具体的代码实现如下。
# 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. """ def search_middle_node(head): """查找链表中间节点 """ # 利用快慢指针 slow = head fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def reverse_list(head): """反转链表 """ # 迭代+双指针 pre = None cur = head while cur: # cur.next, pre, cur = pre, cur, cur.next tmp = cur.next cur.next = pre pre = cur cur = tmp return pre def merge_list(lst1, lst2): """合并链表 """ while lst1 and lst2: tmp_lst1 = lst1.next tmp_lst2 = lst2.next # 依次合并 lst1.next = lst2 lst1 = tmp_lst1 lst2.next = lst1 lst2 = tmp_lst2 if not head: return # 查找中间节点 mid = search_middle_node(head) # 切分 lst1 = head lst2 = mid.next mid.next = None # 逆序 lst2 lst2 = reverse_list(lst2) # 合并两个链表 merge_list(lst1, lst2)时间复杂度： O ( N ) O(N) O(N)， N N N 是链表的节点数。
空间复杂度： O ( 1 ) O(1) O(1)，只用了常数个变量。
公众号 【书所集录】
如有错误，烦请指出，欢迎指点交流。
