各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 53 天。今天力扣上的每日一题是「92. 反转链表 II」。

解题思路

这个题明显是「206. 反转链表」的进阶版，所以请在做出本题前，保证自己能做出 206 题。

反转链表问题的难点在于指针的指向修改，其实只要理清楚思路，一般不会出错的。链表题目建议自己在纸上画一画。

今天的翻转指定区间的链表，需要以下指针：
1. 指向 left 左边元素的指针 pre ，它表示未翻转的链表，需要把当前要翻转的链表结点放到 pre 之后。
2. cur 指向当前要翻转的链表结点。

  1. nxt 指向 cur.next ，表示下一个要被翻转的链表结点。
  2. tail 指向已经翻转的链表的结尾，用它来把已翻转的链表和剩余链表进行拼接。

具体的翻转过程如下面的动图所示，指针虽然多，但是每个指针的移动都有自己的规则的，所以逐个指针去维护，应该不难。

代码

代码中的哑节点 dummy：

创建 哑节点 作为 链表 的新开头，返回结果是这个节点的下一个位置。目的是：如果要翻转的区间包含了原始链表的第一个位置，那么使用 dummy 就可以维护整个翻转的过程更加通用。

  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution(object):
  7.     def reverseBetween(self, head, left, right):
  8.         count = 1
  9.         dummy = ListNode(0)
  10.         dummy.next = head
  11.         pre = dummy
  12.         while pre.next and count < left:
  13.             pre = pre.next
  14.             count += 1
  15.         cur = pre.next
  16.         tail = cur
  17.         while cur and count <= right:
  18.             nxt = cur.next
  19.             cur.next = pre.next
  20.             pre.next = cur
  21.             tail.next = nxt
  22.             cur = nxt
  23.             count += 1
  24.         return dummy.next
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* reverseBetween(ListNode* head, int m, int n) {
  12.         int pos = 1;
  13.         ListNode* dummy = new ListNode(0);
  14.         dummy->next = head;
  15.         ListNode* pre = dummy;
  16.         ListNode* cur = head;
  17.         while (cur && pos < m) {
  18.             pre = pre->next;
  19.             cur = cur->next;
  20.             pos ++;
  21.         }
  22.         ListNode* tailNode = cur;
  23.         while (cur && pos <= n) {
  24.             ListNode* nxt = cur->next;
  25.             cur->next = pre->next;
  26.             pre->next = cur;
  27.             tailNode->next = nxt;
  28.             cur = nxt;
  29.             pos ++;
  30.         }
  31.         return dummy->next;
  32.     }
  33. };
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

刷题心得

  • 这个题是我们春节期间的模拟面试挑选的题目。
    - 如果输入的数据 [m,n] 不一定满足 1 ≤ m ≤ n ≤ 链表长度。那么该怎么做呢？

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！