题解 | #重排链表#

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

#
#
# @param head ListNode类
# @return void
# 如果直接照搬c语言的解法应该也是可以实现的，但是python应该用python的解法。


class Solution:
    def count_num(self, head):
        count = 0
        while head != None:
            count += 1
            head = head.next
        return count

    def reorderList(self, head):
        # write code here
        if head is None or head.next is None or head.next.next is None:
            return head
        front = []
        back = []
        count = self.count_num(head)
        # 创建两个列表分别保存列表中前半部分和后半部分。
        for i in range(count):
            data = head
            head = head.next
            data.next = None
            if (count + 1) // 2 > i:
                front.append(data)
            else:
                back.append(data)

        # 反转第二部分列表
        back.reverse()

        # 将back列表插入front
        lens = len(front)
        j = 0
        for i in range(lens - 1):
            front.insert(2 * i + 1, back[j])
            j += 1

        if front[-1] != back[-1]:
            front.append(back[-1])

        # 将列表中的数据串联成一个链表。
        head = front
        for i in range(count - 1):
            front[i].next = front[i + 1]