LinkList7

题目描述[原题链接][https://leetcode-cn.com/problems/reverse-linked-list-ii/]

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

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

示例:

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

算法描述

​ 把给定的区间的链表节点进行反转，首先找到反转的起始位置，这里要注意是不是头节点，头节点需要进行单独考虑，找到开始位置后，后面的操作就是惯用的三节点操作，改变每一个节点的指向，直到完成区间的反转；要注意的问题就是如果从头结点开始反转需要考虑这个特殊情况，下面上代码：

C++代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(head==NULL)return NULL;
        ListNode *prev=NULL,*cur=head;
        while(m>1){
            prev=cur;
            cur=cur->next;
            m--;
            n--;
        }
        ListNode* three = NULL;
        
        ListNode *tail=cur,*con=prev;
        while(n>0){
            three = cur->next;
            cur->next = prev;
            prev=cur;
            cur=three;
            n--;
        }
        if(con!=NULL){
            con->next=prev;
        }else head = prev;
        tail->next = cur;
        return head;
    }
};

Java代码

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null||head.next==null)return head;
        ListNode prev = null;
        ListNode cur = null;
        cur = head;
        while(m>1){
            prev = cur;
            cur = cur.next;
            m--;
            n--;
        }
        ListNode three=null;
        ListNode tail=cur,con=prev;
        while(n>0){
            three=cur.next;
            cur.next=prev;
            prev=cur;
            cur=three;
            n--;
        }
        if(con!=null){
            con.next=prev;
        }else {
            head=prev;
        }
        tail.next=cur;
        return head;
    }
}