leetcode Reverse Linked List II

题目链接：reverse-linked-list-ii

题目描述

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

翻译

从第m个结点到第n个结点翻转一个链表。只能就地实现（in-place），并且只循环一次（in one-pass）。

例如：

给出如下链表：1->2->3->4->5->NULL, m = 2 ， n = 4,

返回 1->4->3->2->5->NULL.

注意：

参数m,n满足以下条件：

1 ≤ m ≤ n ≤ 链表长度。

分析

• 输入为特殊链表：链表为空，或者只有一个结点。则不需翻转，直接返回链表头指针。

• 此题需要注意四个特殊结点：m-1,m,n,n+1。翻转结束，
  Node(m-1)->next=n
Node(m)->next=n+1

  特殊情况：如果不存在第m-1个结点（即m=1），则返回的头结点是Node(n)。

代码

/**
 * 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(head==NULL||head->next==NULL){
    return head;
}
else{
    ListNode *pre=NULL,*cur=head;
    for(int i=1;i<m;i++){
        pre=cur;
        cur=cur->next;
    }
    //pre是第m-1个结点，cur是第m个结点
    ListNode *new_head=cur;//new_head为翻转子链表的头结点
    ListNode *next=NULL;//next为cur的下一个链表
    ListNode *begin=cur;//begin是第m个结点
    cur=cur->next;
    for(int j=m;j<n;j++){
        next=cur->next;
        cur->next=new_head;
        new_head=cur;
        cur=next;
    }//new_head指向第n个结点
    ListNode *end=cur;//end指向第n+1个结点
    begin->next=end;//Node(m)->next=n+1
    if(pre){
        pre->next=new_head;//如果m!=1,Node(m-1)->next=n
    }
    else{
        head=new_head;//如果m==1，返回子链表的头结点
    }
    return head;
}
}
};