知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 30 - 重排链表 ## 题目(LeetCode 143) 将 L0→L1→...→Ln 重排为 L0→Ln→L1→Ln-1→... ## 解法:找中点 + 反转后半 + 合并 ```java class Solution { public void reorderList(ListNode head) { // 1. 找中点 ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } // 2. 反转后半部分 ListNode second = reverse(slow.next); slow.next = null; // 3. 交替合并 ListNode first = head; while (second != null) { ListNode tmp1 = first.next, tmp2 = second.next; first.next = second; second.next = tmp1; first = tmp1; second = tmp2; } } private ListNode reverse(ListNode head) { ListNode prev = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } } ``` ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 三步走:找中点、反转后半、交替合并。 ## 说明 重排链表的三步法(找中点 + 反转后半 + 交替合并)是最优解,O(n) 时间 O(1) 空间。 另一种思路是用数组存储所有节点,然后用双指针重新连接,但需要 O(n) 额外空间。当前三步法已是最优。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入