Leetcode 92-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

  这题利用了翻转链表的1的知识，只不过需要实现头拼接和尾拼接。为了实现头拼接和尾拼接，需要找四个关键的节点，反转点m和m前一个点，反转点n和n后的第一个点，将m连至n+1，n连到m-1。另外还需要注意头节点，写起来感觉很麻烦，算是刷链表题碰到最麻烦的一题了。

  先贴上代码。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        
        if(head==null||head.next==null)
        {
            return head;
        }
        
        if(m==n)
        {
            return head;
        }
     
        ListNode pre=new ListNode(0);//现在前一位
        ListNode cur=head;//现在一位
        ListNode gra=new ListNode(0);//头节点
        ListNode last=null;//n后一位
        gra.next=head;        
        pre=gra;
        while(cur!=null)
        {
            if(m==1)
            {
              ListNode normal=cur;   
              last=reverse(cur,pre,n);
              normal.next=last;
              break;
            }
            pre=pre.next;
            cur=cur.next;
            m--;
            n--;
            
        }
        
        return gra.next;
        
        
    }
    
    public ListNode reverse(ListNode mhead,ListNode phead,int n)
    {
        ListNode p=null;
        ListNode q=mhead;
        while(n>0)
        {
            ListNode temp=q.next;
            q.next=p;
            p=q;
            q=temp;
            n--;
        
        }
        phead.next=p;
    return q;     
    }    
   
    
}

 注意点有很多：

1.pre是m-1,cur是m，q是n+1,p是n；

2.在反转时，由于是m=1进入的，而n肯定比m大，所以n起码为2,（一开始没想明白）；第一次反转是以null开始的，所有n=2，实际上只反转了当前节点的后一个节点（也可以理解成把当前节点和后面的节点反转了）。

3.当m=1时，gra顺着pre指向p，也就是n点为头节点。m!=1时，gra和pre分离，gra依然指向头结点。（这里想了半天怎么找头结点）。

 

上结论图：