链表指定区间反转-java

解题思路

将链表分为三个部分：前m-1个节点、中间n-m+1个节点、第n个节点之后的部分

Step1: 前m-1个节点尾插法插入到新的链表
Step2: 以Step1的结果的最后一个结点作为头将中间n-m+1个以头插法插入，并记录尾结点。
Step3: 将剩余部分拼接到Step2的结果尾结点后。

    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode p1 = newHead;

        // 尾插法插入m-1个节点
        for(int i=1; i<m && null != p1; ++i) {
            p1 = p1.next;
        }

        // 头插法插入 n-m+1个节点
        ListNode cur = p1.next;
        p1.next = null;

        ListNode tail = null;
        for(int i=1; i<= n-m+1 && cur != null; ++i) {
            ListNode tempNode = cur;
            cur = cur.next;
            tempNode.next = p1.next;
            p1.next = tempNode;
            // 记录头插法产生端的尾结点
            if(null == tail) {
                tail = tempNode;
            }
        }

        tail.next = cur;
        return newHead.next;
    }