Leetcode 92 Reverse Linked List II 4ms 100% Solution

Leetcode 92 Reverse Linked List II 4ms 100% Solution

本题的要求是”Do it in one-pass“，所以首先遍历一遍链表记录下需要反转的部分再插回去的方案是不可行的。

变量定义：

为了防止移位过程中的指针丢失，我们需要三个指针p，q，r（代表连续的三个指针，但不一定以next相连）来记录当前的状态，同时还需要用begin记录下反转部分开始的前一个节点的指针，以及反转部分的第一个节点的指针mp。

算法示意图：

基本思想为在移位过程中记录下关键的指针位置，在反转过程中通过三个指针完成反转：

1. 反转：
   q -> p

2. 移位：
   p = q
   q = r
   r = r->next

3. 首尾重连：
   begin -> p
   mp -> q

下面是c++源代码：

/**
 * 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) {
        //if m == n, no need to reverse.
        if(m == n) return head;
        ListNode *p, *q, *r, *begin, *mp;
        p = new ListNode(0);
        p->next = head;
        q = p->next;
        r = q->next;
        int calc = 1;
        while(calc != m) {
            //forward.
            p = q;
            q = r;
            r = r->next;
            calc ++;
        }
        begin = p;
        mp = q;
        //forward.
        p = q;
        q = r;
        if(r != nullptr) r = r->next;
        while(calc != n) {
            //reverse.
            q->next = p;
            //forward.
            p = q;
            q = r;
            if(r != nullptr) r = r->next;
            calc ++;
        }
        //begin-end relink.
        begin->next = p;
        mp->next = q;
        if(1 == m) {
            return begin->next;
        }
        else {
            return head;
        }

    }
};