1. Description

Reverse a linked list from position m to n. Do it in-place and in one-pass.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

2. Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

3. Code

public class LeetCode0092 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m >= n) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;

        int count = 1;
        while (count < m && pre.next != null) {
            count++;
            pre = pre.next;
        }

        ListNode first = pre;
        pre = pre.next;
        ListNode p = pre.next;

        while (count < n && p != null) {
            pre.next = p.next;
            p.next = first.next;
            first.next = p;
            p = pre.next;
            count++;
        }

        return dummy.next;
    }
}