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.

思路：

感觉自己的思路太啰嗦，那也放这儿吧，记录一下：

用index时刻关注位置，看是否到达m或者n。

当没有到达m的时候，只需向后移动指针，到达m的时候，要断开左右两部分指针。

然后用头插法在左边链表最后的位置插入m到n之间的结点。

需要格外注意的就是边界的情况。

ListNode* reverseBetween(ListNode* head, int m, int n) {     ListNode dumb(0);     dumb.next = head;     if(m == n) return head;     ListNode* preM = &dumb;//保存m之前结点     ListNode* pM = head,*pN = head ,*temp = head;     int index=1;     while(pN != NULL)     {         if(index < m)         {             index++;             preM = pM;             pM = pM->next;             pN = pN->next;         }         else if(index >= m && index <= n)         {             temp = pN->next;             pN->next = preM->next;             preM->next =pN;             pN = temp;             index++;         }         else if(index > n)        break;     }        pM->next = pN;   return dumb.next;}

ListNode *reverseBetween2(ListNode *head, int m, int n) {    if(m==n)return head;    n-=m;    ListNode prehead(0);    prehead.next=head;    ListNode* pre=&prehead;    while(--m)pre=pre->next;    ListNode* pstart=pre->next;    while(n--)    {        ListNode *p=pstart->next;        pstart->next=p->next;        p->next=pre->next;        pre->next=p;    }    return prehead.next;}

参考：