给定一个单链表 L1​→L2​→⋯→Ln−1​→Ln​，请编写程序将链表重新排列为 Ln​→L1​→Ln−1​→L2​→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。 输入格式：

这道题可以使用快慢指针找到链表的中点，然后将链表分为两部分，将后半部分反转，最后将两个链表合并即可。具体实现可以参考下面的代码：

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

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return
        
        # 快慢指针找到链表的中点
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 将后半部分反转
        prev, curr = None, slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # 合并两个链表
        p1, p2 = head, prev
        while p2.next:
            tmp = p1.next
            p1.next = p2
            p1 = tmp
            
            tmp = p2.next
            p2.next = p1
            p2 = tmp
    
    def printList(self, head: ListNode) -> None:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        print(res)