题解 | 链表内指定区间反转

1、解题思路

1. 定位反转区间：首先找到第 m-1 个节点（即反转区间的前一个节点），记为 pre。然后定位到第 m 个节点，记为 start，这是反转区间的第一个节点。定位到第 n 个节点，记为 end，这是反转区间的最后一个节点。记录 end 的下一个节点 next，以便反转后连接剩余链表。
2. 反转区间：将 start 到 end 之间的节点进行反转。反转后，start 将成为反转区间的最后一个节点，end 将成为反转区间的第一个节点。
3. 重新连接链表：将 pre 的 next 指向 end（反转后的第一个节点）。将 start 的 next 指向 next（反转区间后的第一个节点）。
4. 特殊情况处理：如果 m == 1，即从链表头开始反转，此时 pre 为 nullptr，需要特殊处理。

2、代码实现

C++

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        if (head == nullptr || m == n) {
            return head;
        }

        ListNode dummy(0), *pre = &dummy;
        dummy.next = head;

        // 移动到第 m-1 个节点
        for (int i = 1; i < m; ++i) {
            pre = pre->next;
        }

        ListNode* start = pre->next;   // 第 m 个节点, 反转区间的第一个节点
        ListNode* end = start;  // 第 n 个节点, 反转区间的最后一个节点

        // 移动到第 n 个节点
        for (int i = m; i < n; ++i) {
            end = end->next;
        }

        ListNode* next = end->next; // 第 n+1 个节点
        end->next = nullptr;    // 切断反转区间

        // 反转区间
        ListNode* prev = nullptr;
        ListNode* cur = start;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }

        // 重新连接链表
        pre->next = end;    // pre 指向反转后的头节点 (原 end)
        start->next = next; //反转后的尾节点 （原 start) 指向 next

        return dummy.next;
    }
};

Java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if (head == null || m == n) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        // 移动到第 m-1 个节点
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }

        ListNode start = pre.next;  // 第 m 个节点，反转区间的第一个节点
        ListNode end = start;       // 第 n 个节点，反转区间的最后一个节点

        // 移动到第 n 个节点
        for (int i = m; i < n; i++) {
            end = end.next;
        }

        ListNode next = end.next;   // 第 n+1 个节点
        end.next = null;            // 切断反转区间

        // 反转区间
        ListNode prev = null;
        ListNode curr = start;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        // 重新连接链表
        pre.next = end;    // pre 指向反转后的头节点（原 end）
        start.next = next; // 反转后的尾节点（原 start）指向 next

        return dummy.next;
    }
}

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @param m int整型
# @param n int整型
# @return ListNode类
#
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        if not head or m == n:
            return head

        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        # 移动到第 m-1 个节点
        for _ in range(1, m):
            pre = pre.next

        start = pre.next  # 第 m 个节点，反转区间的第一个节点
        end = start  # 第 n 个节点，反转区间的最后一个节点

        # 移动到第 n 个节点
        for _ in range(m, n):
            end = end.next

        next_node = end.next  # 第 n+1 个节点
        end.next = None  # 切断反转区间

        # 反转区间
        prev = None
        curr = start
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        # 重新连接链表
        pre.next = end  # pre 指向反转后的头节点（原 end）
        start.next = next_node  # 反转后的尾节点（原 start）指向 next_node

        return dummy.next

3、复杂度分析

• 时间复杂度：O(n)，最多遍历链表两次。
• 空间复杂度：O(1)，仅使用固定数量的额外指针。