反转链表II

七崽爱吃小饼干2026/01/07阅读 0专栏算法合集

反转链表II

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

示例 1：

codeType

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

示例 2：

codeType

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

提示：

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

进阶：你可以使用一趟扫描完成反转吗？

解法：

该解法相当于先把3转到2前面，再把4转到3前面。更清晰易懂的解法可以用栈来解决。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    // 1. 创建虚拟头节点（避免处理左边界是头节点的特殊情况）
    const dummy = new ListNode(0);
    dummy.next = head;
    
    // 2. 定位到左边界的前驱节点（pPrev）：遍历 left-1 次
    let pPrev = dummy;
    for (let i = 0; i < left - 1; i++) {
        pPrev = pPrev.next; 
    }

    // 3. 定位到左边界节点（pCurr）：反转的起始节点
    let pCurr = pPrev.next;
    
    // 4. 头插法反转 [left, right] 区间：共反转 right-left 次
    for (let i = 0; i < right - left; i++) {
        // 取出当前节点的下一个节点（待插入的节点）
        const pNext = pCurr.next;
        // 步骤1：将 pCurr 指向 pNext 的下一个节点（拆出 pNext）
        pCurr.next = pNext.next;
        // 步骤2：将 pNext 插入到 pPrev 的下一位（头插核心）
        pNext.next = pPrev.next;
        // 步骤3：更新 pPrev 的下一个节点为 pNext
        pPrev.next = pNext;
    }

    // 5. 返回虚拟头节点的下一个节点（整个链表的头）
    return dummy.next;
}