Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Test Cases

Linked list

Input:

(ListNode) head = [1,2,3,4,5]
(int) left = 2
(int) right = 4

Output:

(ListNode) [1,4,3,2,5]

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) return head;
        ListNode prev = null, curr = head;
        while(left > 1) {
            prev = curr;
            curr = curr.next;
            left--;
            right--;
        }

        ListNode tail = curr, conn = prev;
        while(right > 0) {
            ListNode third = curr.next;
            curr.next = prev;
            prev = curr;
            curr = third;
            right--;
        }

        if (conn != null) {
            conn.next = prev;
        } else {
            head = prev;
        }
        tail.next = curr;
        return head;
    }
}
Time Complexity: O(n)
Space Complexity: O(1)