【常见面试算法】反转链表II

问题

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Leetcode网友Alexxx的思路：
以1->2->3->4->5, m = 2, n=4 为例:

定位到要反转部分的头节点 2，head = 2；前驱结点 1，pre = 1；
当前节点的下一个节点3调整为前驱节点的下一个节点 1->3->2->4->5,
当前结点仍为2， 前驱结点依然是1，重复上一步操作。。。
1->4->3->2->5。

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i = 1; i < m; i++){
            pre = pre.next;
        }
        head = pre.next;
        for(int i = m; i < n; i++){t
            ListNode next = head.next;
            head.next = next.next;
            nex.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}

m = 1, n = length的时候，这一解法也是为反转链表I提供了另一个解题思路。