[Leetcode 143] 重排链表

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入是一个单向链表L的头节点head
单向链表L表示为:
请将其重新排列后变为:
不能只是改变节点的值,而是需要实际的交换节点。
 
示例 1:
notion image
示例 2:
notion image

解法一:快慢指针(推荐)

  1. 快慢指针找中点
    1. 想象快指针走两步、慢指针走一步。
      快指针到头时,慢指针正好在链表中间附近。
      中点的下一位,就是“后半段链表”的起点。
  1. 把后半段链表整个反转
    1. 因为我们想从后往前拿元素,但链表不能反向走,所以干脆把后半段整个翻转,这样你就能从新头节点一路向右走,等价于“从后往前取”。
  1. 两段链表交替合并
    1. 前半段:1 → 2 → 3
      反转后半段:5 → 4
      每次把后半段节点插到前半段节点后面,就形成了想要的顺序。
复杂度
  • 时间:O(n) 三次线性遍历(找中点、反转、合并)
  • 空间:O(1)

解法二:栈

  1. 把链表所有节点丢进栈
    1. 栈的特点是后进先出,也就是说你可以轻松从链表尾部不断弹出节点。
  1. 从头开始走链表,每次取一个栈顶插回链表
    1. 但要注意,只需要弹出链表后半段的数量。
      例如链表长度为 n,只需要弹出 (n − 1) // 2 个节点。
  1. 边插边移动指针
    1. 直到处理完后半部分,最后把尾节点的 next 指向 None。
思路简单,不过需要 O(n) 额外空间。
复杂度
  • 时间:O(n)
  • 空间:O(n)

解法三:数组 + 双指针

  1. 把所有节点丢进数组
  1. 双指针 left 从开头走,right 从末尾走
  1. 每次交替取节点,重新连接它们
这跟栈方法差不多,写起来简单,也需要用 O(n) 空间。
复杂度
  • 时间 O(n)
  • 空间 O(n)
上一篇
[Leetcode 138] 随机链表的复制
下一篇
[Leetcode 146] LRU 缓存