题解 | #重排链表#

# 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
        # --------------------#
        # 首先判断head是否为空
        # --------------------#
        if head is None:
            return
        # -------------------------------------#
        # 建立前向和后向数组，并获取head的长度
        # -------------------------------------#
        front = []
        back = []
        count = self.count_num(head)
        # -------------------------------------------#
        # 将题目要求的奇数个存入front,偶数个存入back
        # -------------------------------------------#
        for i in range(count):
            mum = head
            head = head.next
            mum.next = None
            if i < int(count/2)+1:
                front.append(mum)
            else:
                back.append(mum)
        # --------------------#
        # 开始建立新的链表
        # --------------------#
        newhead = front[0]
        temp = newhead
        if count%2 == 1 or count == 2:
            for i in range(len(front)-1):
                if len(back) > 0:
                    temp.next = back[len(back) - i - 1]
                    temp = temp.next
                    temp.next = front[i+1]
                    temp = temp.next
                else:
                    temp.next = front[i+1]
                    temp = temp.next
        else:
            for i in range(len(front)-2):
                temp.next = back[len(back) - i - 1]
                temp = temp.next
                temp.next = front[i+1]
                temp = temp.next
                if i == len(front)-3:
                    temp.next = front[i+2]
                    temp = temp.next
        return newhead
    
    # --------------------#
    # 计算head的长度的函数
    # --------------------#
    def count_num(self, head):
        count = 0
        while head != None:
            count += 1
            head = head.next
        return count