LeetCode——第92题：指定区间内翻转链表（反转链表 II）_链表内指定区间反转

指定区间内翻转链表

题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。

输入：1->2->3->4->5->NULL, m = 2, n = 4

输出：1->4->3->2->5->NULL

这道题的重点是：找到需要翻转的区间
总共需要4个指针，其中1个是添加一个虚拟的头指针（主要是防止需要翻转的是头节点）
剩下的3个指针，分别代表：找到起始位置的前一个指针pre，起始指针start，结尾指针tail
pre和start在找到后都不需要在移动，原因是pre只需要指向区间的最后一个指针即可，start只需要指向区间外的第一个指针，所以都不需要移动
所以只需要移动tail指针，那么tail指针怎么移动的，用start指针的next记录tail指针的下一个位置
详见代码

/*
题目：Reversed Linked List II
*/
/**
 * 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) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            pre = pre->next;
        }
        ListNode* start = pre->next;
        ListNode* tail = start->next;
        for (int i = m; i < n; i++) {
            start->next = tail->next;
            tail->next = pre->next;
            pre->next = tail;
            tail = start->next;
        }
        return dummy->next;
    }
};
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