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

 * 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) {
        // 当链表为空或只有一个节点时直接返回
        if(head == NULL || head->next==NULL){
            return head;
        }
        //辅助指针
        ListNode * cur = head;
        //辅助指针移动到m的前一个节点
        for(int i=0;i<m-2;i++){
            cur = cur->next;
        }
        ListNode * pre = NULL;
        ListNode * tmp_head = head;
        //当m大于1则辅助节点移动到m,临时头节点指向m的上一节点
        if(m>1){
            tmp_head = cur;
            cur = cur->next;
        }
        //辅助翻转的临时指针
        ListNode * tmp;
        //当前指针为翻转后的尾巴
        ListNode * tmp_tail = cur;
        //翻转m-n节点
        for(int j=m-1;j<n;j++){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        //翻转过后cur为尾巴的下一个节点
        tmp_tail->next = cur;
        //如果m>1则cur的上一个节点即pre需要链接到tmp_head
        if(m>1){
            tmp_head->next = pre;
        }
        //此种情况为头到尾都要翻转
        else if(cur == NULL){
            return pre;
        }
        //头到n翻转
        else{
             head = pre; 
        }
        return head;
        
    }
};