【问题描述】: 设线性表L = (a1 ,a2，a3，.…，an-1，an）采用带头结点的单链表保存，请设计一个空间复杂度为 0(1）且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表S＝ (a1，an，a2，an-1，.…）。 【输入形式】：多组数据，每组第一行为n，表示链表的长度。接下来为链表中的元素。不超过5组数据。 【输出形式】：每组数据，输出重新排列后的序列。 【样例输入】 10 11 13 15 17 19 2 4 6 8 20 【样例输出】 11 20 13 8 15 6 17 4 19 2

思路：

1.首先将链表平分成两半，分别是A链表和B链表。

2.将B链表逆序，变成B'链表。

3.依次从A链表和B'链表中取出一个元素，交替放入新链表S中，直到A链表和B'链表都为空。

4.最后将S链表的头结点去掉，即为所求的新链表。

代码实现：

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


def reverse_list(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    pre, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = pre
        pre, cur = cur, nxt
    return pre


def reorder_list(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    l1, l2 = head, reverse_list(mid)
    dummy = ListNode(0)
    cur = dummy
    while l1 and l2:
        cur.next = l1
        l1 = l1.next
        cur = cur.next
        cur.next = l2
        l2 = l2.next
        cur = cur.next
    if l1:
        cur.next = l1
    if l2:
        cur.next = l2
    return dummy.next


if __name__ == '__main__':
    while True:
        try:
            n = int(input())
            nums = list(map(int, input().split()))
            nodes = [ListNode(num) for num in nums]
            for i in range(n-1):
                nodes[i].next = nodes[i+1]
            head = nodes[0]
            res = reorder_list(head)
            while res:
                print(res.val, end=' ')
                res = res.next
            print()
        except:
            break