Medium

题目描述

给你一个单链表的头节点 head，链表如下所示：

L0 → L1 → … → Ln-1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-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^4]
  • 1 <= Node.val <= 1000

解题思路

这道题要求将链表重排为交替取头尾节点的形式。我们可以用几种方法来解决：

方法1：栈辅助（空间复杂度O(n)） 遍历链表将所有节点压入栈中，然后交替从头部和栈顶取节点重新连接。

方法2：数组存储（空间复杂度O(n)） 将所有节点存入数组，利用双指针从两端向中间移动重新连接节点。

方法3：三步法（推荐，空间复杂度O(1)） 这是最优解法，分为三个步骤：

  1. 找到中点：使用快慢指针找到链表的中点
  2. 反转后半部分：将后半部分链表反转
  3. 合并两个链表：将前半部分和反转后的后半部分交替合并

这种方法的优势是只需要O(1)的额外空间，且思路清晰。通过快慢指针技巧找中点是链表问题的经典套路，反转链表和合并链表也是基础操作。整个过程保持了原地操作的要求。

代码实现

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        
        // 1. 找到中点
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;
        
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 断开链表
        prev->next = nullptr;
        
        // 2. 反转后半部分
        ListNode* second = reverse(slow);
        
        // 3. 合并两个链表
        ListNode* first = head;
        while (second) {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;
            
            first->next = second;
            second->next = temp1;
            
            first = temp1;
            second = temp2;
        }
    }
    
private:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
};

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return
        
        # 1. 找到中点
        slow = fast = head
        prev = None
        
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        
        # 断开链表
        prev.next = None
        
        # 2. 反转后半部分
        second = self.reverse(slow)
        
        # 3. 合并两个链表
        first = head
        while second:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first, second = temp1, temp2
    
    def reverse(self, head):
        prev = None
        curr = head
        
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        return prev

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        // 1. 找到中点
        ListNode slow = head, fast = head;
        ListNode prev = null;
        
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 断开链表
        prev.next = null;
        
        // 2. 反转后半部分
        ListNode second = Reverse(slow);
        
        // 3. 合并两个链表
        ListNode first = head;
        while (second != null) {
            ListNode temp1 = first.next;
            ListNode temp2 = second.next;
            
            first.next = second;
            second.next = temp1;
            
            first = temp1;
            second = temp2;
        }
    }
    
    private ListNode Reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

var reorderList = function(head) {
    if (!head || !head.next) return;
    
    // 1. 找到中点
    let slow = head, fast = head;
    let prev = null;
    
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 断开链表
    prev.next = null;
    
    // 2. 反转后半部分
    let second = reverse(slow);
    
    // 3. 合并两个链表
    let first = head;
    while (second) {
        let temp1 = first.next;
        let temp2 = second.next;
        
        first.next = second;
        second.next = temp1;
        
        first = temp1;
        second = temp2;
    }
};

function reverse(head) {
    let prev = null;
    let curr = head;
    
    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
栈辅助O(n)O(n)
数组存储O(n)O(n)
三步法（推荐）O(n)O(1)

三步法是最优解：

  • 时间复杂度：O(n)，需要遍历链表三次（找中点、反转、合并），每次都是O(n)
  • 空间复杂度：O(1)，只使用了常数个额外变量，没有使用额外的数据结构

相关题目