本文共 1505 字，大约阅读时间需要 5 分钟。

单向链表的重新排列问题是一个经典的中等难度算法题目。目标是将原链表L0→L1→…→Ln-1→Ln 重新排列为 L0→Ln→L1→Ln-1→L2→Ln-2→…的形式，而不改变节点的值。

问题分析

给定一个单向链表，我们需要将其重新排列，使得前半部分的节点与后半部分的节点交替出现。例如，给定链表{1,2,3,4}，重新排列后变为{1,4,2,3}。解决这个问题的关键在于找到链表的中点，并将后半部分反转，然后与前半部分交替连接。

解决思路

代码实现

public class ReorderList {    public void reorderList(ListNode head) {        if (head == null || head.next == null) {            return;        }        // 找到中点        ListNode fast = head.next;        ListNode slow = head;        while (fast != null && fast.next != null) {            fast = fast.next.next;            slow = slow.next;        }        // 分离两部分        ListNode p = slow.next;        slow.next = null; // 将慢指针作为前半部分的末尾        // 反转后半部分        ListNode pPre = null;        ListNode pSuf = p.next;        while (p != null) {            pSuf = p.next;            p.next = pPre;            pPre = p;            p = pSuf;        }        // 合并两部分        ListNode l1 = head;        ListNode l2 = pPre;        while (l1 != null && l2 != null) {            ListNode nextL1 = l1.next;            ListNode nextL2 = l2.next;            l1.next = l2;            l2.next = nextL1;            l1 = nextL1;            l2 = nextL2;        }    }}

代码解释

这种方法确保了链表的重新排列过程在原地完成，时间复杂度为O(n)，空间复杂度为O(1)。