Some of the interesting ways to reverse a linked list in place

0 / 2271
reverse linked list in place

In this blog, I will cover some approaches using which, you can reverse linked list in place. Consider we have a linked list marked by the node structure below (in C language)

struct node {

    int data;

    struct node* ptr;

}

 

Below is a recursive approach for reversing the linked list and then printing it.

Below is the code snippet

 

Reverse a linked list in place

 

 

 

 

NODE *result = NULL;
NODE *current = *head;
NODE *next;
while(current != NULL) {
    next = current->link;
    current->link = result;
    result = current;
    current = next;
}
*head = result;  // assign the reverse list back to head node of the list
The result node stores the result (the reversed linked list). Current node points to the current node while traversing and this will be used as an iterator to loop through the linked list. While traversing, we first save the next node to current in a ptr , then we link current node to the result(reverse list marked by NULL value initially as seen). We then store the current node ptr in the result(reverse list) and then increment current node ptr to point to the next node.Eventually, I assign the reverse list back to the head (first node of the list so that the list is reversed in place).
Below is the pictorial representation for better understanding.
1->2->3->4->5->NULL
current = 1
result = NULL
1->NULL
2->1->NULL
3->2->1->NULL
4->3->2->1->NULL
5->4->3->2->1->NULL
Below is the complete code to create/insert/print and reverse a linked list (another approach) using C language

Program to create/insert print and reverse a linked list

 

#include 
#include 

typedef struct node
{
    int data;
    struct node *link;
}NODE;

NODE *newNode = NULL;
NODE *temp = NULL;

void insert(int, NODE**);
void printList(NODE *head);
NODE* reverse(NODE *L);

int main()
{
    int i = 0;
    NODE *firstNode = NULL,
    *head    = NULL;
    
    for(i = 1; i <= 10; i++)
    {
        insert(i, &firstNode);
    }
    
    printf("The original list nn");
    printList(firstNode);
    printf("nn");
    
    head = firstNode;
    
    
    firstNode = reverse(head);
    
    printf("The reversed list nn");
    printList(firstNode);
    printf("nn");
    
    return 0;
}


NODE* reverse(NODE *L)
{
    #if 0
    NODE *first = L;
    NODE *next = L->link;
    
    if(L->link->link != NULL)
    reverse(L->link, &L);
    else
    {
        //    next->link = first;
        //    next->link->link = NULL;
        //    return;
    }
    printf("%d | %dn", first->data, next->data);
    next->link = first;
    #endif
    
    //    NODE *head = L;
    NODE *next = NULL;
    NODE *tmp = NULL;
    
    while (L != NULL)
    {
        tmp = L->link;
        L->link = next;
        next = L;
        L = tmp;
    }
    
    return next;
    
}

void printList(NODE *head)
{
    while(head != NULL){
        printf("%d ", head->data);
        head = head->link;
    }
}



void insert(int data, NODE** head)
{
    
    if(*head == NULL)
    {
        *head = (NODE*)malloc(sizeof(NODE));
        (*head)->data = data;
        (*head)->link = NULL;
    }
    else
    {
        newNode = (NODE*)malloc(sizeof(NODE));
        newNode->data = data;
        newNode->link = NULL;
        
        temp = *head;
        
        while(temp->link != NULL)
        temp = temp->link;
        
        temp->link = newNode;
    }
}

Feel free to comment, if you have any doubts or queries.

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.
loading...

Related Posts