题解 | #重排链表#

用列表存储每个节点，依次弹出首位、末位的节点，组成新链表即可。 没有新建链表，空间复杂度O(n),时间复杂度O(2n)=O(n)

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

#
# 
# @param head ListNode类 
# @return void
#
class Solution:
    def reorderList(self , head ):
        # write code here
        if head is None:
            return None
        link=[]
        while head!=None:
            tmp=head
            head=head.next
            tmp.next=None
            link.append(tmp)
            
        newhead=link.pop(0)
        tmp=newhead
        front=False
        while len(link)>0:
            if front:
                tmp.next=link.pop(0)
                front=False
            else:
                tmp.next=link.pop()
                front=True
            tmp=tmp.next
        return newhead