尧图网页设计 
LeetCode 143. 重排链表 — Rust 实现思路经典三步走策略原地 O(1) 额外空间不算指针找中点先求链表长度 len则前半段长度为 len/2找到前半段最后一个节点并断开。反转后半段标准的链表反转。交替合并把反转后的后半段逐节点插入到前半段之间。以 L0→L1→L2→L3→L4 为例· 前半段 L0→L1后半段 L2→L3→L4· 反转后半段 L4→L3→L2· 交替合并 → L0→L4→L1→L3→L2 ✅代码#[derive(PartialEq, Eq, Clone, Debug)]pubstructListNode{pubval:i32,pubnext:OptionBoxListNode,}implListNode{#[inline]fnnew(val:i32)-Self{ListNode{next:None,val}}}structSolution;implSolution{pubfnreorder_list(head:mutOptionBoxListNode){// 1. 计算链表长度letmutlen0;letmutcurhead.as_ref();whileletSome(node)cur{len1;curnode.next.as_ref();}iflen2{return;}// 找到前半段最后一个节点第 len/2 个节点letmidlen/2;letmutcurhead.as_mut().unwrap();for_in0..mid-1{curcur.next.as_mut().unwrap();}// 2. 断开后半段并反转letmutsecondcur.next.take();letmutprev:OptionBoxListNodeNone;whileletSome(mutnode)second{letnextnode.next.take();node.nextprev;prevSome(node);secondnext;}letmutsecondprev;// 3. 交替合并两个链表letmutfirsthead.take();letmutdummyBox::new(ListNode::new(0));letmuttailmutdummy;letmuttake_firsttrue;whilefirst.is_some()second.is_some(){iftake_first{letmutnodefirst.take().unwrap();firstnode.next.take();tail.nextSome(node);}else{letmutnodesecond.take().unwrap();secondnode.next.take();tail.nextSome(node);}tailtail.next.as_mut().unwrap();take_first!take_first;}// 接上剩余的必然是 second 剩余因为前半段长度 ≤ 后半段tail.nextiffirst.is_some(){first}else{second};*headdummy.next;}}复杂度项 值时间复杂度 O(n) — 遍历三次空间复杂度 O(1) — 仅指针操作关键点解析为什么循环结束后只可能剩 secondmid len/2前半段长度 ⌊n/2⌋后半段 ⌈n/2⌉。所以后半段 ≥ 前半段交替合并时前半段一定先用完。保险起见代码仍写成 if first.is_some() { first } else { second }。Rust 借用处理小技巧· 用 head.as_mut().unwrap() 得到 mut Box在循环里不断 cur cur.next.as_mut().unwrap() 前进避免重复借用 head。· 断开后半段用 cur.next.take()把所有权从 Option 中偷出来。· 合并时用 dummy 哨兵节点简化边界处理。早退条件 len 2长度 0/1/2 时重排结果与原链表相同。另一种更直观的写法借用 Vec如果面试不要求 O(1) 空间可以先收集所有节点引用/值到 Vec再两指针重建pubfnreorder_list(head:mutOptionBoxListNode){letmutvalsVec::new();letmutcurhead.as_ref();whileletSome(node)cur{vals.push(node.val);curnode.next.as_ref();}let(muti,mutj)(0usize,vals.len());letmutdummyBox::new(ListNode::new(0));letmuttailmutdummy;letmuttake_fronttrue;whileij{letviftake_front{letxvals[i];i1;x}else{j-1;vals[j]};tail.nextSome(Box::new(ListNode::new(v)));tailtail.next.as_mut().unwrap();take_front!take_front;}*headdummy.next;}写法更简单但空间 O(n)。原地面试场合推荐第一种。 DeepSeek LeetCode 143. 重排链表 Rust实现
LeetCode 143. 重排链表 — Rust 实现思路经典三步走策略原地 O(1) 额外空间不算指针找中点先求链表长度 len则前半段长度为 len/2找到前半段最后一个节点并断开。反转后半段标准的链表反转。交替合并把反转后的后半段逐节点插入到前半段之间。以 L0→L1→L2→L3→L4 为例· 前半段 L0→L1后半段 L2→L3→L4· 反转后半段 L4→L3→L2· 交替合并 → L0→L4→L1→L3→L2 ✅代码#[derive(PartialEq, Eq, Clone, Debug)]pubstructListNode{pubval:i32,pubnext:OptionBoxListNode,}implListNode{#[inline]fnnew(val:i32)-Self{ListNode{next:None,val}}}structSolution;implSolution{pubfnreorder_list(head:mutOptionBoxListNode){// 1. 计算链表长度letmutlen0;letmutcurhead.as_ref();whileletSome(node)cur{len1;curnode.next.as_ref();}iflen2{return;}// 找到前半段最后一个节点第 len/2 个节点letmidlen/2;letmutcurhead.as_mut().unwrap();for_in0..mid-1{curcur.next.as_mut().unwrap();}// 2. 断开后半段并反转letmutsecondcur.next.take();letmutprev:OptionBoxListNodeNone;whileletSome(mutnode)second{letnextnode.next.take();node.nextprev;prevSome(node);secondnext;}letmutsecondprev;// 3. 交替合并两个链表letmutfirsthead.take();letmutdummyBox::new(ListNode::new(0));letmuttailmutdummy;letmuttake_firsttrue;whilefirst.is_some()second.is_some(){iftake_first{letmutnodefirst.take().unwrap();firstnode.next.take();tail.nextSome(node);}else{letmutnodesecond.take().unwrap();secondnode.next.take();tail.nextSome(node);}tailtail.next.as_mut().unwrap();take_first!take_first;}// 接上剩余的必然是 second 剩余因为前半段长度 ≤ 后半段tail.nextiffirst.is_some(){first}else{second};*headdummy.next;}}复杂度项 值时间复杂度 O(n) — 遍历三次空间复杂度 O(1) — 仅指针操作关键点解析为什么循环结束后只可能剩 secondmid len/2前半段长度 ⌊n/2⌋后半段 ⌈n/2⌉。所以后半段 ≥ 前半段交替合并时前半段一定先用完。保险起见代码仍写成 if first.is_some() { first } else { second }。Rust 借用处理小技巧· 用 head.as_mut().unwrap() 得到 mut Box在循环里不断 cur cur.next.as_mut().unwrap() 前进避免重复借用 head。· 断开后半段用 cur.next.take()把所有权从 Option 中偷出来。· 合并时用 dummy 哨兵节点简化边界处理。早退条件 len 2长度 0/1/2 时重排结果与原链表相同。另一种更直观的写法借用 Vec如果面试不要求 O(1) 空间可以先收集所有节点引用/值到 Vec再两指针重建pubfnreorder_list(head:mutOptionBoxListNode){letmutvalsVec::new();letmutcurhead.as_ref();whileletSome(node)cur{vals.push(node.val);curnode.next.as_ref();}let(muti,mutj)(0usize,vals.len());letmutdummyBox::new(ListNode::new(0));letmuttailmutdummy;letmuttake_fronttrue;whileij{letviftake_front{letxvals[i];i1;x}else{j-1;vals[j]};tail.nextSome(Box::new(ListNode::new(v)));tailtail.next.as_mut().unwrap();take_front!take_front;}*headdummy.next;}写法更简单但空间 O(n)。原地面试场合推荐第一种。