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

链表翻转 
需要前面增加一个节点preHead
而且返回的时候需要考虑到返回的是preHead.next，因为可能head节点也被翻转到最后了，

代码如下：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode preHead = new ListNode(10000);
        preHead.next = head;
        ListNode cur = preHead;
        ListNode pPre = null, qNext = null;
        ListNode p = null, q = null;
        int count = -1;
        while(cur != null){
            count++;
            if(count == m-1){
                pPre = cur;
                p = cur.next;
            }
            if(count == n){
                q = cur;
                qNext = q.next;
            }
            cur = cur.next;
        }
        reverse(p,q);
        pPre.next = q;
        p.next = qNext;
        //return head;
        return preHead.next;
    }
    import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode preHead = new ListNode(10000);
        preHead.next = head;
        ListNode cur = preHead;
        ListNode pPre = null, qNext = null;
        ListNode p = null, q = null;
        int count = -1;
        while(cur != null){
            count++;
            if(count == m-1){
                pPre = cur;
                p = cur.next;
            }
            if(count == n){
                q = cur;
                qNext = q.next;
            }
            cur = cur.next;
        }
        reverse(p,q);
        pPre.next = q;
        p.next = qNext;
        //return head;
        return preHead.next;
    }
    public void reverse(ListNode p, ListNode q){
        ListNode cNext = p.next;
        ListNode cur = p;
        while(cur != q){
            System.out.print(cNext.val);
            ListNode temp = cNext.next;
            cNext.next = cur;
            cur = cNext;
            cNext = temp;
        }
    }
}