Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list‘s nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
这个题目思路就是先用[LeetCode] 876. Middle of the Linked List_Easy tag: Linked List去找到中点，然后利用[LeetCode] 206. Reverse Linked List_Easy tag: Linked List将后半截reverse，
接着利用类似于[LeetCode] 21. Merge Two Sorted Lists_Easy tag: Linked List的方法去将前后半截merge起来即可。
Code:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if not head or not head.next or not head.next.next: return # find middle, if length is odd, then front slow, fast = head, head while fast: if fast.next is None or fast.next.next is None: break slow = slow.next fast = fast.next.next head2 = slow.next slow.next = None # reverse head2 pre = None while head2: temp = head2.next head2.next = pre pre = head2 head2 = temp # merge head and pre while head and pre: temp1, temp2 = head.next, pre.next head.next = pre pre.next = temp1 head = temp1 pre = temp2
[LeetCode] 143. Reorder List_Middle tag: Linked List
原文：https://www.cnblogs.com/Johnsonxiong/p/10804499.html