92. Reverse Linked List II

// LeetCode URL: https://leetcode.com/problems/reverse-linked-list-ii/

//   Definition for singly-linked list.
// class ListNode {
//     int val;
//     ListNode next;

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

/**
 * One Pass Solution
 *
 * Time Complexity: O(min(L, n))
 *
 * Space Complexity: O(1)
 *
 * L = Length of the list (Total Number of nodes). n = input index n.
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m < 1) {
            m = 1;
        }
        if (n < 1) {
            n = 1;
        }
        if (head == null || head.next == null || m == n) {
            return head;
        }

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode current = head;
        ListNode previous = dummyHead;
        int count = 1;
        while (current != null && count < m) {
            previous = current;
            current = current.next;
            count++;
        }

        if (current == null || current.next == null) {
            return head;
        }

        ListNode nodeBeforeM = previous;
        ListNode nodeAtM = current;

        previous = null;
        while (current != null && count <= n) {
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
            count++;
        }

        nodeBeforeM.next = previous;
        nodeAtM.next = current;

        return dummyHead.next;
    }
}