Can I change node values instead of pointers in Reorder List?

No, the problem requires manipulating the actual nodes. Altering values violates constraints and won't be accepted.

What is the easiest way to find the midpoint of a singly linked list?

Use slow and fast pointers: slow moves one node at a time, fast moves two. When fast reaches the end, slow is at midpoint.

Do I need extra space to reorder the list?

An in-place solution requires O(1) extra space, but using a stack or recursion will increase space usage.

How do I merge two halves without losing nodes?

Always store next references before reassigning pointers, and alternate nodes from each half until all nodes are merged.

Is Reorder List considered a Linked-list pointer manipulation pattern?

Yes, the core challenge is rearranging pointers without changing node values, which exemplifies the linked-list pointer manipulation pattern.

#143

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为： L 0 → L 1 → … → L n - 1 → L n 请将其重新排列后变为： L 0 → L n → L 1 → L n - 1 → L 2 → L n - 2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。…

链表双指针栈递归

题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L₀ → L₁ → … → L_{n - 1} → L_n

请将其重新排列后变为：

L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 2} → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 10⁴]
1 <= node.val <= 1000

lightbulb

解题思路

方法一：快慢指针 + 反转链表 + 合并链表

我们先用快慢指针找到链表的中点，然后将链表的后半部分反转，最后将左右两个链表合并。

时间复杂度 $O(n)$ ，其中 $n$ 是链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # 快慢指针找到链表中点
        fast = slow = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # cur 指向右半部分链表
        cur = slow.next
        slow.next = None

        # 反转右半部分链表
        pre = None
        while cur:
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        cur = head

        # 此时 cur, pre 分别指向链表左右两半的第一个节点
        # 合并
        while pre:
            t = pre.next
            pre.next = cur.next
            cur.next = pre
            cur, pre = pre.next, t

speed

复杂度分析

指标	值
时间	complexity is O(n) because each node is visited a constant number of times during split, reverse, and merge. Space complexity is O(1) for in-place reversal and merging, though recursion or a stack can increase space usage if used.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate can split the list efficiently without extra space.
question_mark
Watch for correct in-place reversal of the second half.
question_mark
Ensure merging maintains the alternating pattern without node loss.

warning

常见陷阱

外企场景

error
Modifying node values instead of pointers, which violates the problem constraints.
error
Losing reference to the second half while splitting, leading to memory leaks.
error
Incorrect merging order causing cycles or skipped nodes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reorder list using recursion instead of iterative merge.
arrow_right_alt
Reorder list using a stack to store the second half for interleaving.
arrow_right_alt
Modify the pattern to L0 → Ln → L1 → Ln-1 → L2 → ... only for odd-length lists.

help

常见问题

外企场景

继续练习

#234 回文链表 #142 环形链表 II #141 环形链表