题解 | #链表内指定区间反转#

关键点： 1、时间复杂度为O(1)，所以只能遍历1次链表； 2、注意边界,m和n为链表开头和结尾时，返回值（表示反转后的链表头）应该是哪个;

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode *start = nullptr, *end = nullptr, *start_prev = nullptr, *cur = nullptr, *prev = nullptr, *next = nullptr;
        int i = 0;
       
        prev = head;
        for (i = 0, cur = head; i < n && cur != nullptr; i++, cur = next) {
            next = cur->next;
            if (i < m - 1) {
                //if (i == m - 2) {
                //    start_prev = cur;
                //}
                prev = cur;
                continue;
            }
            
            if ( i == m - 1) {
                start = cur;
                start_prev = prev;
                prev = cur;
                continue;
            }
           
            cur->next = prev;
            prev = cur;
        }
        if ( i < n) {
            return NULL;
        }
        end = prev;
        if (start_prev != start) {
            start_prev->next = end;
            start->next = cur;
             return head;
        } else {
            start->next = cur;
            return end;
        } 
    }
};