Program to reverse a Linked List in C

C++, Uncategorized / June 16, 2021 / sumitsuthar94 / 0

A linked list is a data structure used for storing a collection of elements in a linear order. In a linked list, each element (known as a node) contains a value and a pointer to the next element in the list. The first element in the list is called the head, and the last element is called the tail.

Unlike an array, which uses contiguous memory locations to store its elements, a linked list uses separate memory locations for each node and connects them using pointers. This means that adding or removing an element from a linked list does not require moving any other elements, unlike in an array where shifting elements is required.

Linked lists can be singly linked, where each node contains a pointer to the next node in the list, or doubly linked, where each node contains a pointer to both the next and previous nodes in the list. Singly linked lists are simpler and require less memory, while doubly linked lists allow for more efficient traversal in both directions.

Linked lists are commonly used in computer science and programming because of their flexibility and efficient insertions and deletions. They are used in various applications, such as implementing stacks, queues, and hash tables.

To reverse a linked list in C, you can use the following code:

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void printList(Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* curr = head;
    Node* next = NULL;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("Original list: ");
    printList(head);

    head = reverseList(head);

    printf("Reversed list: ");
    printList(head);

    return 0;
}

In this code, we define a Node struct to represent a node in the linked list, and a createNode() function to create a new node with the given data. We also define a printList() function to print the elements of the linked list.

The reverseList() function takes the head of the linked list as input and returns the head of the reversed linked list. It uses three pointers prev, curr, and next to reverse the links between the nodes in the list.

In the main() function, we create a sample linked list and print it using printList(). We then reverse the list using reverseList() and print the reversed list using printList().

beginner, C, coding, interview questions, programming

sumitsuthar94