92. 反转链表 II（java链表）

题目

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

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

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

代码

/**
 * 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) {
        ListNode root = new ListNode(0), p, q, r = null;
        int cnt = 0;
        root.next = head;
        p = root;
        q = head;
        while (q != null) {
            cnt++;
            if (cnt < m) {
                p = q;
                q = q.next;
            } else if (cnt == m) {
                r = q;
                q = q.next;
            } else if (cnt <= n) {
                ListNode t = q;
                q = q.next;
                t.next = p.next;
                p.next = t;
            } else
                break;
        }
        if (r != null)
            r.next = q;
        return root.next;
    }
}