Reverse Linked List - C Solution

1. Introduction

This blog post addresses a fundamental problem in C programming and data structures: reversing a singly linked list. Reversing a linked list is a common task in software development and is a critical concept in understanding linked list operations, which have applications in numerous areas of computer science and data processing.

Problem

Given the head of a singly linked list, the task is to reverse the list and return the head of the reversed list. This problem tests our ability to manipulate pointers and understand the structure of linked lists.

2. Solution Steps

1. Initialize three pointers: previous, current, and next.

2. Iterate through the list. At each step:

- Save the next node (current->next).

- Reverse the current node's link (point current->next to previous).

- Move the previous and current pointers one step forward.

3. At the end, previous will point to the new head of the reversed list.

4. Return previous as the head of the reversed list.

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 linked list
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *current = head;
    struct ListNode *next = NULL;

    while (current != NULL) {
        next = current->next;  // Save the next node
        current->next = prev;  // Reverse the link
        prev = current;        // Move prev to current node
        current = next;        // Move to the next node
    }
    return prev; // Prev is the new head of the reversed list
}

// Utility function to create a new node
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 demonstrate reverseList function
int main() {
    // Create a sample list: 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);

    head = reverseList(head); // Reverse the list

    // Print the reversed list
    printf("Output: ");
    while (head != NULL) {
        printf("%d ", head->val);
        struct ListNode* temp = head;
        head = head->next;
        free(temp); // Free the node after printing
    }
    printf("\n");

    return 0;
}

Output:

5 4 3 2 1

Explanation:

The program starts with a linked list 1->2->3->4->5. 

The reverseList function iteratively reverses the list by changing the next pointers of the nodes. 

At each step, it takes care not to lose the rest of the list, which is done by keeping track of the next node before changing the link. 

Finally, the list is reversed to 5->4->3->2->1, and this reversed list is printed as the output. 

This example demonstrates the fundamental operations on linked lists and the importance of pointer manipulation in C programming.