Last updated on January 19th, 2025 at 10:48 pm

Here, we see a Reverse Linked List II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Linked List

Level of Question

Medium

Reverse Linked List II LeetCode Solution

1. Problem Statement

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.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “In-place Reversal of a LinkedList”. This pattern is commonly used when we need to reverse a portion of a linked list without using extra space for another data structure. The key idea is to reverse the links between nodes in the specified range while maintaining the connections to the rest of the list.

3. Code Implementation in Different Languages

3.1 Reverse Linked List II C++

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
       ListNode *dummy = new ListNode(0), *pre = dummy, *cur;
       dummy -> next = head;
       for (int i = 0; i < left - 1; i++) {
           pre = pre -> next;
       }
       cur = pre -> next;
       for (int i = 0; i < right - left; i++) {
           ListNode* temp = pre -> next;
           pre -> next = cur -> next;
           cur -> next = cur -> next -> next;
           pre -> next -> next = temp;
       }
       return dummy -> next;        
    }
};

3.2 Reverse Linked List II Java

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
    if(head == null) return null;
    ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
    dummy.next = head;
    ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
    for(int i = 0; i<left-1; i++) pre = pre.next;
    
    ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
    ListNode then = start.next; // a pointer to a node that will be reversed

    for(int i=0; i<right-left; i++)
    {
        start.next = then.next;
        then.next = pre.next;
        pre.next = then;
        then = start.next;
    }
    return dummy.next;        
    }
}

3.3 Reverse Linked List II JavaScript

var reverseBetween = function(head, left, right) {
    let current = head, start = head, position = 1;
    
    while(position < left) {
        start = current
        current = current.next;
        position ++;
    }
    
    let reversedList = null,  tail = current;
    
    while(position >= left && position <= right) {
        const next = current.next;
        current.next = reversedList;
        reversedList = current;
        current = next;
        position ++
    }
    start.next = reversedList;
    tail.next = current;
    return left > 1 ? head : reversedList    
};

3.4 Reverse Linked List II Python

class Solution(object):
    def reverseBetween(self, head, left, right):
        if left == right:
            return head

        dummyNode = ListNode(0)
        dummyNode.next = head
        pre = dummyNode

        for i in range(left - 1):
            pre = pre.next
        
        reverse = None
        cur = pre.next
        for i in range(right - left + 1):
            next = cur.next
            cur.next = reverse
            reverse = cur
            cur = next

        pre.next.next = cur
        pre.next = reverse
        return dummyNode.next

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

• The code efficiently reverses a portion of a linked list in-place.
• It uses a dummy node to handle edge cases and simplifies pointer manipulation.
• The algorithm is optimal in terms of both time and space complexity.