题目链接

92. 反转链表 II

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
image.png
进阶： 你可以使用一趟扫描完成反转吗？

解题思路

1. 「哨兵」节点 + 头插法

常规思路：将 [left, right] 区间链表断开，反转后再拼接回原链表。当 left 和 right 分为别头尾节点时，断链需要遍历一遍链表，反转需要遍历一遍链表。增加了时间复杂度的常数时间。

下面是只使用一趟扫描的解法：找到 left 位置节点（称为cur）的前一个节点称为 pre，然后将 cur 后面的节点依次头插到 cur 节点之前。

  1. class Solution {
  2.     public ListNode reverseBetween(ListNode head, int left, int right) {
  3.         ListNode dummy = new ListNode(-1);
  4.         dummy.next = head;
  5.         ListNode pre = dummy;
  6.         // pre：left 位置节点的前一个节点
  7.         for (int i = 1; i < left; i++) {
  8.             pre = pre.next;
  9.         }
  10.         ListNode cur = pre.next;
  11.         for (int i = left; i < right; i++) {
  12.             ListNode temp = cur.next;
  13.             cur.next = temp.next;
  14.             temp.next = pre.next;
  15.             pre.next = temp;
  16.         }
  17.         return dummy.next;
  18.     }
  19. }
  • 时间复杂度：LeetCode92. 反转链表 II - 图2
  • 空间复杂度：LeetCode92. 反转链表 II - 图3