题目链接：92. 反转链表 II

题解：

又是链表操作题，记得要画图哦！

题目简述：

将一个链表的m ~ n位置进行翻转！

题解：

思路：

  • 将m ~ n进行指针翻转
  • 将m指向n的下一位， 将a指向n

如下图：

具体来说：

  • 首先找到m的前一个位置a
  • 让b指向m， c指向m的下一位，t指向c的下一位
  • 接下来将m ~ n进行指针翻转，即让c指向b
  • 然后b c指针顺次后移
  • 最后将该链如上图所示，连起来！懒得解释了，看图吧！

时间复杂度：O(n)

AC代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto a = dummy;
        for(int i = 0; i < m - 1; i++) a = a->next;
        auto b = a->next, c = b->next;
        for(int i = 0; i < n - m; i++){
            auto t= c->next;
            c->next = b;
            b = c, c = t;
        }
        auto t = a->next;
        a->next = b;
        t->next = c;
        return dummy->next;
    }
};