Medium

题目描述

给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

约束条件：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶： 你能在一次遍历中完成吗？

解题思路

解题思路

这道题要求反转链表中指定区间的节点，是链表反转的经典变形。

方法一：一次遍历（推荐） 核心思想是先定位到需要反转的区间，然后在该区间内进行链表反转操作。

具体步骤：

  1. 使用虚拟头节点简化边界处理
  2. 先遍历到 left-1 位置，记录前驱节点 prev
  3. 从 left 位置开始，连续执行 right-left 次头插法操作
  4. 头插法：将当前节点的下一个节点插入到 prev 的后面

方法二：三段式处理 将链表分为三段：前段（1到left-1）、中段（left到right，需反转）、后段（right+1到末尾）。先断开连接，反转中段，再重新连接三段。

方法三：递归处理 使用递归的方式处理区间反转，但空间复杂度较高。

推荐使用方法一，因为它只需一次遍历，时间复杂度最优，且代码相对简洁。

代码实现

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        
        // 移动到left前一个位置
        for (int i = 0; i < left - 1; i++) {
            prev = prev->next;
        }
        
        ListNode* curr = prev->next;
        
        // 执行right-left次头插操作
        for (int i = 0; i < right - left; i++) {
            ListNode* next = curr->next;
            curr->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }
        
        return dummy->next;
    }
};

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        
        # 移动到left前一个位置
        for i in range(left - 1):
            prev = prev.next
        
        curr = prev.next
        
        # 执行right-left次头插操作
        for i in range(right - left):
            next_node = curr.next
            curr.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node
        
        return dummy.next

public class Solution {
    public ListNode ReverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        // 移动到left前一个位置
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        
        ListNode curr = prev.next;
        
        // 执行right-left次头插操作
        for (int i = 0; i < right - left; i++) {
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

var reverseBetween = function(head, left, right) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    
    // 移动到left前一个位置
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    
    let curr = prev.next;
    
    // 执行right-left次头插操作
    for (let i = 0; i < right - left; i++) {
        let next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历一次链表，n为链表长度
空间复杂度O(1)只使用常数级别的额外空间

相关题目