题目如下：

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.

解题思路：我的方法是用一个list保存链表后半部分的节点，接下来从头开始遍历链表，把list中的第一个节点插入到原链表的第一个节点后，第二个插入到原链表的第二个节点后面，直到list全部节点都插入到原链表为止。

代码如下：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def reorderList(self, head):        """        :type head: ListNode        :rtype: None Do not return anything, modify head in-place instead.        """        if head == None:            return        mid,tail = head,head        while tail != None:            tail = tail.next            if tail == None:                break            tail = tail.next            if tail == None:                break            mid = mid.next        l = []        second_half = mid.next        mid.next = None        while second_half != None:            l.insert(0,second_half)            second_half = second_half.next        current = head        while len(l) > 0:            node = l.pop(0)            node.next = current.next            current.next = node            current = current.next.next