DeepSeek LeetCode 143. 重排链表 Python3实现

LeetCode 143「重排链表」要求将链表 L0→L1→…→Ln-1→Ln 重新排列为 L0→Ln→L1→Ln-1→L2→Ln-2→…且不能只改变节点值。思路三步走O(1) 空间找中点快慢指针慢指针最终指向前半部分的最后一个节点。反转后半部分从中点的下一个节点开始反转链表。合并两个链表将前半部分与反转后的后半部分交替拼接。Python3 实现# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defreorderList(self,head:Optional[ListNode])-None: Do not return anything, modify head in-place instead. ifnotheadornothead.next:return# 1. 快慢指针找中点slow 指向前半部分最后一个节点slow,fasthead,headwhilefast.nextandfast.next.next:slowslow.nextfastfast.next.next# 2. 反转后半部分prev,curNone,slow.nextwhilecur:nxtcur.nextcur.nextprev prevcur curnxt# 断开前后两半slow.nextNone# 3. 交替合并两个链表first,secondhead,prevwhilesecond:tmp1,tmp2first.next,second.nextfirst.nextsecond second.nexttmp1 first,secondtmp1,tmp2复杂度分析指标 值时间复杂度 O(n)三次遍历链表空间复杂度 O(1)只用了常数个指针关键点· 找中点时循环条件 fast.next and fast.next.next 保证偶数节点时 slow 停在前半部分末尾。· 反转后 prev 是后半部分的头节点。· 合并时先保存 first.next 和 second.next再修改指针避免断链。