Reverse Linked List II - Practice Coding Problems

Reverse Linked List II - Problem

Linked List Medium

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.

The positions are 1-indexed.

Input & Output

Example 1 — Basic Reversal

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

› Output: [1,4,3,2,5]

💡 Note: Reverse nodes from position 2 to 4: 2→3→4 becomes 4→3→2, while nodes 1 and 5 remain in place

Example 2 — Single Node

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

› Output: [5]

💡 Note: Only one node and reversing position 1 to 1 means no change needed

Example 3 — Full List Reversal

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

› Output: [5,3]

💡 Note: Reverse the entire list from position 1 to 2: 3→5 becomes 5→3

Constraints

The number of nodes in the list is n
1 ≤ n ≤ 500
-500 ≤ Node.val ≤ 500
1 ≤ left ≤ right ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [1,2,3,4,5] with left=2, right=4

Process

Reverse nodes from position 2 to 4

Output

Resulting list [1,4,3,2,5]

Key Takeaway

🎯 Key Insight: Use three pointers to reverse links while maintaining connections to unreversed parts

Asked in

f Facebook 45 a Amazon 38 M Microsoft 32 G Google 28

The optimal approach uses three-pointer technique to reverse the sublist in-place. Key insight: maintain connections to unreversed parts while reversing links one by one. Best approach is one-pass pointer reversal with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ One-Pass Pointer Reversal	O(n)	O(1)	Reverse the sublist in-place using three pointers without extra space
Convert to Array and Back	O(n)	O(n)	Convert linked list to array, reverse the subarray, then rebuild the linked list

One-Pass Pointer Reversal — Algorithm Steps

Step 1: Find the node just before position left
Step 2: Reverse links from left to right using three pointers
Step 3: Reconnect the reversed section to the rest of the list

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Position

Navigate to the node before position left

Reverse Links

Use prev, curr, next pointers to reverse connections

Reconnect

Link reversed section back to the rest of the list

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head, int left, int right) {
    if (!head || left == right) return head;
    
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    struct ListNode* prevLeft = dummy;
    
    for (int i = 0; i < left - 1; i++) {
        prevLeft = prevLeft->next;
    }
    
    struct ListNode* prev = prevLeft->next;
    struct ListNode* curr = prev->next;
    
    for (int i = 0; i < right - left; i++) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    prevLeft->next->next = curr;
    prevLeft->next = prev;
    
    return dummy->next;
}

int* listToArray(struct ListNode* head, int* returnSize) {
    int* result = (int*)malloc(5000 * sizeof(int));
    *returnSize = 0;
    struct ListNode* curr = head;
    while (curr) {
        result[(*returnSize)++] = curr->val;
        curr = curr->next;
    }
    return result;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* curr = head;
    for (int i = 1; i < size; i++) {
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->val = arr[i];
        curr->next->next = NULL;
        curr = curr->next;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int headArr[500];
    int headSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        headArr[headSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int left, right;
    scanf("%d", &left);
    scanf("%d", &right);
    
    struct ListNode* head = arrayToList(headArr, headSize);
    struct ListNode* resultHead = solution(head, left, right);
    int resultSize;
    int* result = listToArray(resultHead, &resultSize);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("%d", result[i]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find position and reverse the sublist

✓ Linear Growth

Space Complexity

O(1)

Only uses a constant number of pointer variables

✓ Linear Space

587.0K Views

High Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One-Pass Pointer Reversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler