Reverse Linked List II

92. 反转链表II

分析

创建一个虚拟头节点 dummy，它的 next 指向 head，简化边界情况处理（如 left = 1）
用指针 p 找到 left 节点的前一个节点
从 p->next 开始反转区间 [left, right] 的节点，采用头插法实现
反转完成后，将前后链表重新接好

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    ListNode* reverseBetween(ListNode* head, int left, int right)
    {
      ListNode* dummy = new ListNode(-1); // 创建虚拟头节点，简化边界处理
      dummy->next = head;

      ListNode* p = dummy;
      // 将 p 移动到 left 前一个节点的位置
      for (int i = 0; i < left - 1; ++ i)
        p = p->next;

      // 初始化要反转的部分的起始节点
      ListNode *prev = p->next, *cur = prev->next;

      // 头插法反转 [left, right] 区间
      for (int i = 0; i < right - left; ++ i)
      {
        ListNode *next = cur->next; // 暂存下一个节点
        cur->next = prev;           // 当前节点指向前一个节点
        prev = cur, cur = next;     // 向前推进指针
      }

      // 拼接反转后的子链表与剩余链表
      ListNode *q = p->next; // 反转前的 left 节点，反转后变成尾部
      p->next = prev;        // p 指向反转后的头部
      q->next = cur;         // 原 left 节点指向反转后剩余的部分

      return dummy->next;    // 返回新链表头节点
    }
};