先找到list的中点, 把后半部分reverse, 再merge前半部分list和后半部分list。

Find the middle node of the list, then reverse the second half of the list, then merge the first half list and the second half list.

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return nothing
    def reorderList(self, head):
        if head == None or head.next == None: return
        # find middle node
        fast = slow = head
        while True:
            if fast.next: fast = fast.next
            else: break
            if fast.next: fast, slow = fast.next, slow.next
            else: break
        # reverse the second half list
        prev, curr, head2, slow.next = slow.next, slow.next.next, slow.next, None
        while curr:
            prev.next, curr.next, head2 = curr.next, head2, curr 
            curr = prev.next
        # join the first half and the second half
        dummy2 = ListNode(0)
        dummy2.next, head2 = head2, dummy2 # add a dummy node to second half list
        prev1, curr1, prev2, curr2 = head, head.next, head2, head2.next
        while curr2:
            # insert curr2 node to first half list
            prev2.next, prev1.next, curr2.next = curr2.next, curr2, curr1 
            curr2 = prev2.next
            prev1 = curr1
            if prev1 == None: break
            curr1 = prev1.next