链表重排序算法详解：字节跳动面试题的完整解析

问题背景

字节跳动的技术面试中经常出现链表操作题目。这道重排序问题考查了多个核心知识点。面试官希望看到最优解法和清晰的思路分析。

题目内容

我们有一个单链表 L：L0→L1→…→Ln-1→Ln。要把它重新排列成：L0→Ln→L1→Ln-1→L2→Ln-2→…

注意，我们不能简单修改节点的值。需要真正交换节点的位置。

看几个例子：

例子1：
原链表：1→2→3→4→5
结果：1→5→2→4→3

例子2：
原链表：1→2→3→4
结果：1→4→2→3

解题思路分析

这道题目包含了链表操作的几个经典技巧。我们需要观察最终结果的规律。

仔细看重排后的链表，它其实是两部分的交错拼接：

• 前半部分保持原顺序
• 后半部分反转后与前半部分交替连接

这样我们就有了清晰的解题步骤：

1. 找到链表的中点
2. 把后半部分反转
3. 把两部分交错合并

具体实现方法

第一步：寻找链表中点

我们用快慢指针来找中点。设置两个指针 slow 和 fast，都从头开始。

// slow 每次走一步，fast 每次走两步
while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}

当 fast 到达末尾时，slow 就指向了中点。

对于链表 1→2→3→4→5→6：

• slow 最终指向节点 3
• 前半部分：1→2→3
• 后半部分：4→5→6

第二步：反转后半部分

我们把中点后面的链表反转过来。使用标准的链表反转算法：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

第三步：交错合并两个链表

现在我们有了两个链表：

• 左边：1→2→3
• 右边：6→5→4（已反转）

我们把它们交错连接起来：

while (leftHead != null && rightHead != null) {
    // 保存下一个要处理的节点
    ListNode leftNext = leftHead.next;
    ListNode rightNext = rightHead.next;
    
    // 连接当前节点
    leftHead.next = rightHead;
    rightHead.next = leftNext;
    
    // 移动到下一个节点
    leftHead = leftNext;
    rightHead = rightNext;
}

完整代码实现

class Solution {
    public void reorderList(ListNode head) {
        // 找到链表中点
        ListNode mid = findMiddle(head);
        
        // 分割链表
        ListNode leftHead = head;
        ListNode rightHead = mid.next;
        mid.next = null;
        
        // 反转右半部分
        rightHead = reverseList(rightHead);
        
        // 交错合并
        mergeLists(leftHead, rightHead);
    }
    
    // 寻找链表中点
    public ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    // 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
    
    // 交错合并两个链表
    public void mergeLists(ListNode left, ListNode right) {
        while (left != null && right != null) {
            ListNode leftNext = left.next;
            ListNode rightNext = right.next;
            
            left.next = right;
            right.next = leftNext;
            
            left = leftNext;
            right = rightNext;
        }
    }
}

核心技术要点

时间复杂度： O(n)，我们遍历链表三次（找中点、反转、合并）

空间复杂度： O(1)，只用了几个额外的指针变量

关键技巧：

1. 快慢指针找中点是链表题的经典方法
2. 递归反转链表要注意断开原有连接
3. 合并时要先保存下一个节点的位置

这道题目综合运用了链表操作的多个核心技术。掌握了这些基础技巧，面对其他链表问题也会更有信心。