链表中等2 种解法

#143重排链表

把 L0 → L1 → … → Ln 原地重排为 L0 → Ln → L1 → Ln-1 → …，不能只交换节点值。

#链表#双指针#栈

原题

给定一个单链表 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

查看原题

解题主线

数组法将单向链表转化为可双端访问的节点序列，重连过程直观。
原地法由找前半段尾节点、反转后半段、交替合并三步组成。

解法 1：数组双指针

把节点引用存入数组，用左右指针按首、尾、次首、次尾的顺序重连。

时间复杂度： O(n)
空间复杂度： O(n)

JAVA

import java.util.ArrayList;
import java.util.List;

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public void reorderList(ListNode head) {
        // 重排只改变 next 指向，所有原节点必须各出现一次且不复制节点值。
        // 每轮按未处理区间的首、尾各消费一个节点，保持结果前缀已符合交替顺序。
        if (head == null) return;
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode current = head; current != null; current = current.next) {
            nodes.add(current);
        }
        int left = 0;
        int right = nodes.size() - 1;
        while (left < right) {
            nodes.get(left++).next = nodes.get(right);
            if (left == right) break;
            nodes.get(right--).next = nodes.get(left);
        }
        nodes.get(left).next = null;
    }
}

解法 2：中点 + 反转 + 交替合并

从前半段尾部断开，反转后半段，再将两个链表的节点交替连接。

时间复杂度： O(n)
空间复杂度： O(1)

JAVA

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public void reorderList(ListNode head) {
        // 重排只改变 next 指向，所有原节点必须各出现一次且不复制节点值。
        // 每轮按未处理区间的首、尾各消费一个节点，保持结果前缀已符合交替顺序。
        if (head == null || head.next == null) return;

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode second = reverse(slow.next);
        slow.next = null;
        ListNode first = head;
        while (second != null) {
            ListNode firstNext = first.next;
            ListNode secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode previous = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = previous;
            previous = head;
            head = next;
        }
        return previous;
    }
}

实现提示

改用前半段尾节点作为切分点，并补齐空链表与单节点保护。

边界与易错点

重排完成后必须让最终尾节点指向 null，否则可能保留旧边并形成环。
旧原地实现对空链表会访问 mid.next 而空指针；展示代码先处理长度小于 2 的情况。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q143_reorderList.java