92-reverse-linked-list-ii.md

92. Reverse Linked List II - 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

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

---

题目标签：Linked List

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	4 ms	868.4 KB

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
static auto _ = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (n == m) { return head; }
        ListNode* guard = new ListNode(0);
        guard->next = head;
        ListNode* st = guard;
        for (int i=0; i<m-1; ++i) {
            st = st->next;
        }
        ListNode* p = st;
        ListNode* q = p->next;
        ListNode* r = q->next;
        for (int i=0; i<n-m; ++i) {
            p = q;
            q = r;
            r = r->next;
            q->next = p;
        }
        st->next->next = r;
        st->next = q;
        return guard->next;
    }
};