leetcode:反转链表 II

题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

题目链接：反转链表 II

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路和代码实现

//思路，双指针法。并且需要借助一个新的节点,pre节点表示待移动节点的前一个节点，cur表示移动节点，
    // next表示待移动节点的下一个节点，每次移动将next节点移动到pre节点后
    //例如本题移动过程如下 原始节点1->2->3->4->5->NULL
    //第一次 1(pre) 2(cur) 3(next) 4 5 ->1 3 2 4 5
    //第二次 1(pre) 3 2(cur) 4(next) 5 ->1 4 3 2 5
    //****************(本题的重要点在于cur和pre保持固定不变，每次使next移动到pre之后)*********************************
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode newcode = new ListNode(-1);
        newcode.next = head;
        ListNode pre = newcode;

        //将pre移动到待移动节点的前一个节点，并且以后固定不动
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;//cur以后固定不变
        //移动节点，每次将next节点移动到pre节点之后
        for (int i = m; i < n; i++) {
            ListNode next = cur.next;
            //cur.next指向next后面的部分
            cur.next=next.next;
            next.next=pre.next;//next.next指向pre的next，也就是最新的第m个位置
            pre.next=next;//更新next为最新的第m个位置
        }
        return newcode.next;
    }