题目描述（中等难度）

给定链表的一个范围，将这个范围内的链表倒置。

解法一

首先找到 m 的位置，记录两端的节点 left1 和 left2 。

然后每遍历一个节点，就倒置一个节点。

到 n 的位置后，利用之前的 left1 和 left2 完成连接。

为了完成链表的倒置需要两个指针 pre 和 head。为了少考虑边界条件，例如 m = 1 的倒置。加一个哨兵节点 dummy。

当前状态用图形描述

倒转链表，将 h 的 next 指向 p，并且后移 p 和 h。

然后上边一步会重复多次，直到 h 到达 n 的位置。当然这道题比较特殊，上图 h 已经到达了 n 的位置。

此时，我们需要将 h 指向 p，同时将 l1 指向 h，l2 指向 h.next，使得链表接起来。

92. Reverse Linked List II - 图1

操作完成，将 dummy.next 返回即可。

  2.     if (m == n) {
  3.         return head;
  4.     }
  5.     ListNode dummy = new ListNode(0);
  6.     dummy.next = head;
  7.     int count = 0;
  8.     ListNode left1 = null;
  9.     ListNode left2 = null;
  10.     ListNode pre = dummy;
  11.         count++;
  13.         if (count == m) {
  14.             left1 = pre;
  15.             left2 = head;
  16.         }
  17.         // m 和 n 之间，倒转链表
  18.         if (count > m && count < n) {
  19.             ListNode temp = head.next;
  20.             head.next = pre;
  21.             pre = head;
  22.             head = temp;
  24.         //到达 n
  25.         if (count == n) {
  26.             left2.next = head.next;
  27.             head.next = pre;
  28.             left1.next = head;
  29.             break;
  30.         }
  31.         //两个指针后移
  32.         head = head.next;
  33.         pre = pre.next;
  34.     }
  35. }

空间复杂度：O（1）。

总

考察链表知识，如果对链表很熟悉，在纸上画一画，理清楚怎么指向，很快可以写出来。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情