Reverse Linked List II - C Solution

1. Introduction

In this post, we delve into a more challenging problem in linked list manipulation - "Reverse Linked List II". This problem extends the basic concept of reversing a linked list by focusing on reversing a subsection of the list. It's a great exercise in understanding advanced linked list operations in C programming.

Problem

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

2. Solution Steps

1. Create dummy node dummyHead and point its next to the head of the list.

2. Initialize pointers prev and curr to start reversing from the left position.

3. Traverse the list till left to position prev and curr.

4. Reverse the sublist from left to right.

5. Adjust the pointers to reconnect the reversed sublist with the rest of the list.

6. Return the new head of the list, which is dummyHead->next.

3. Code Program

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

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Function to reverse a part of the linked list
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    struct ListNode dummyHead;
    dummyHead.next = head;
    struct ListNode *prev = &dummyHead, *curr;

    // Move prev to the node before the start of the reversal
    for (int i = 0; i < left - 1; i++) {
        prev = prev->next;
    }

    curr = prev->next;
    // Reverse the sublist
    for (int i = 0; i < right - left; i++) {
        struct ListNode *temp = curr->next;
        curr->next = temp->next;
        temp->next = prev->next;
        prev->next = temp;
    }

    return dummyHead.next;
}

// Helper function to create a new ListNode
struct ListNode* newNode(int val) {
    struct ListNode* node = (struct ListNode*) malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to test the reverseBetween function
int main() {
    // Create and initialize linked list for demonstration: [1 -> 2 -> 3 -> 4 -> 5]
    struct ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    // Call function and print the modified list
    struct ListNode* result = reverseBetween(head, 2, 4);
    printf("Reversed List: ");
    while (result != NULL) {
        printf("%d ", result->val);
        struct ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

Output:

Reversed List: 1 4 3 2 5

Explanation:

1. reverseBetween starts by creating a dummy head for ease of manipulation.

2. The list is traversed until prev is just before the left position.

3. The sublist is reversed in-place by adjusting the pointers.

4. The main function demonstrates this with an example list, reversing nodes from position 2 to 4.

5. It prints the reversed list and frees the allocated memory.