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

/**
 * 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
        int cnt=0;
        ListNode *p=head;
        ListNode *begin=NULL,*cur,*end=NULL;
        while(p!=NULL){
            cnt++;
            if(cnt==m-1) begin=p;
            if(cnt==m) cur=p;
            // if(cnt==n) cur2=p;
            if(cnt==n+1) end=p;
            p=p->next;
        }
        ListNode *pre=NULL,*cur1=cur;;
        while(cur!=end){
            ListNode *tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        cur1->next=end;
        if(begin!=NULL){
            begin->next=pre;
            return head;
        }
        return pre;
    }
};

首先要通过原链表得到几个关键节点信息：

begin：翻转区间的前一个节点，可能为NULL

cur：翻转区间的第一个节点

end：翻转的区间的后一个节点，用作判定循环结束的标志，可能为NULL

翻转部分当成普通的翻转链表来写，pre依旧为NULL，但是终止条件变为链表第n+1个节点，即end。

翻转后还需要接入原链表，此时需要判断翻转的第一个节点是不是链表头节点：

1.若翻转第一个节点是链表头节点，直接返回翻转的最后一个节点pre；

2.若不是，则将翻转后的链表接入begin节点后，返回head。

时间复杂度：O(n)，空间复杂度O(1)