Reorder List

总共三件事，第一快慢指针找到中点，第二将中点之后的链表反过来，第三将两个链表合并

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        dummy = ListNode('a')
        dummy.next = head

        slow, fast = dummy, dummy
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        left, right = head, self.reverse(slow.next)
        while right:
            node = right
            right = right.next
            tmp = left.next
            left.next = node
            node.next = tmp
            left = tmp

    def reverse(self, root):
        pre, nxt = None, None
        while root:
            nxt = root.next
            root.next = pre
            pre = root
            root = nxt
        return pre