面试重排链表python

我可以回答这个问题。重排链表可以使用快慢指针找到链表中点，然后将后半部分链表翻转，最后将两个链表交替合并即可。具体实现可以参考以下代码：

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.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # 翻转后半部分链表
        pre, cur = None, slow.next
        slow.next = None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        # 合并两个链表
        p1, p2 = head, pre
        while p2:
            nxt1, nxt2 = p1.next, p2.next
            p1.next = p2
            p2.next = nxt1
            p1, p2 = nxt1, nxt2

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。