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.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    if (head == NULL) return head;
    struct ListNode *prev = NULL, *curr = head;
    while(left > 1) {
        prev = curr;
        curr = curr->next;
        left--;
        right--;
    }

    struct ListNode* tail = curr, *conn = prev;
    while (right > 0) {
        struct 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;
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), 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;
    }
};
/**
 * 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)