Download Our Beta Android App And Help Us Build Awesome Stuff!  Download Now.

Reverse linked list C

reverse.txt
File size: 2.13 KB

File content type: text/plain

Category: Assignment

Course: B.Tech.

Semester: 3, 4, and 7

#include <stdio.h>

struct Node 
{ 
    int data; 
    struct Node* next; 
}; 
  
/* Function to reverse the linked list */
static void reverse(struct Node** head_ref) 
{ 
    struct Node* prev   = NULL; 
    struct Node* current = *head_ref; 
    struct Node* next = NULL; 
    while (current != NULL) 
    { 
        // Store next 
        next  = current->next;   
  
        // Reverse current node's pointer 
        current->next = prev;    
  
        // Move pointers one position ahead. 
        prev = current; 
        current = next; 
    } 
    *head_ref = prev; 
}

/* Function to push a node */
void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
            (struct Node*) malloc(sizeof(struct Node));            
    new_node->data  = new_data; 
    new_node->next = (*head_ref);     
    (*head_ref)    = new_node; 
} 
  
/* Function to print linked list */
void printList(struct Node *head) 
{ 
    struct Node *temp = head; 
    while(temp != NULL) 
    { 
        printf("%d  ", temp->data);     
        temp = temp->next;   
    } 
}

void recursiveReverse(struct Node** head_ref) 
{ 
    struct Node* first; 
    struct Node* rest; 
       
    /* empty list */
    if (*head_ref == NULL) 
       return;    
  
    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref;   
    rest  = first->next; 
  
    /* List has only one node */
    if (rest == NULL) 
       return;    
  
    /* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest); 
    first->next->next  = first;   
      
    /* tricky step -- see the diagram */
    first->next  = NULL;           
  
    /* fix the head pointer */
    *head_ref = rest;               
}


/* Driver program to test above function*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
    
     push(&head, 20); 
     push(&head, 4); 
     push(&head, 15);  
     push(&head, 85);       
      
     printf("Given linked list\n"); 
     printList(head);     
     recursiveReverse(&head);                       
     printf("\nReversed Linked list \n"); 
     printList(head);     
     getchar(); 
} 

Added by passhojao

Comments