R7-1 重排链表 分数 14 作者 陈越 单位 浙江大学 给定一个单链表 L1​→L2​→⋯→Ln−1​→Ln​，请编写程序将链表重新排列为 Ln​→L1​→Ln−1​→L2​→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

好的，我的回答如下：

可以使用快慢指针找到链表的中点，然后将链表分为两部分，将后半部分反转，最后将两个链表合并即可。

具体步骤如下：
1. 使用快慢指针找到链表的中点，将链表分为两部分；
2. 将后半部分反转；
3. 将两个链表合并。

代码实现如下：

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 head
        
        # 快慢指针找到链表的中点
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 将链表分为两部分
        l1, l2 = head, slow.next
        slow.next = None
        
        # 将后半部分反转
        prev, curr = None, l2
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # 将两个链表合并
        while l1 and l2:
            l1_next = l1.next
            l2_next = l2.next
            
            l1.next = l2
            l2.next = l1_next
            
            l1 = l1_next
            l2 = l2_next