链表中等2 种解法

#143重排链表

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

#链表#双指针#栈

解题主线

数组法将单向链表转化为可双端访问的节点序列，重连过程直观。

原地法由找前半段尾节点、反转后半段、交替合并三步组成。

解法 1：数组双指针

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

时间复杂度

O(n)

空间复杂度

O(n)

143. 重排链表 · 数组双指针

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) {
        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)

143. 重排链表 · 中点 + 反转 + 交替合并

java

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

    public void reorderList(ListNode head) {
        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