{"id":27260,"date":"2018-01-20T20:41:50","date_gmt":"2018-01-20T15:11:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27260"},"modified":"2018-01-20T20:41:50","modified_gmt":"2018-01-20T15:11:50","slug":"write-function-reverse-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/write-function-reverse-linked-list\/","title":{"rendered":"C Algorithm – Write a function to reverse a linked list"},"content":{"rendered":"

Given pointer to the head node of a linked list, the task is to reverse the linked list.<\/p>\n

Examples<\/strong>:<\/p>\n

Input : Head of following linked list  \r\n       1->2->3->4->NULL\r\nOutput : Linked list should be changed to,\r\n       4->3->2->1->NULL\r\n\r\nInput : Head of following linked list  \r\n       1->2->3->4->5->NULL\r\nOutput : Linked list should be changed to,\r\n       5->4->3->2->1->NULL\r\n\r\nInput : NULL\r\nOutput : NULL\r\n\r\nInput  : 1->NULL\r\nOutput : 1->NULL<\/pre>\n
\n[ad type=”banner”]\n
Iterative Method<\/strong>
\nIterate trough the linked list. In loop, change next to prev, prev to current and current to next<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
#include<stdio.h>#include<stdlib.h> \/* Link list node *\/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;    while (current != NULL)    {        next  = current->next;          current->next = prev;           prev = current;        current = next;    }    *head_ref = prev;} \/* Function to push a node *\/void push(struct node** head_ref, int new_data){    \/* allocate node *\/    struct node* new_node =            (struct node*) malloc(sizeof(struct node));                \/* put in the data  *\/    new_node->data  = new_data;                    \/* link the old list off the new node *\/    new_node->next = (*head_ref);                \/* move the head to point to the new node *\/    (*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;      }}     \/* 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);         reverse(&head);                           printf("\\nReversed Linked list \\n");     printList(head);         getchar();}<\/code><\/pre> <\/div>\n
Given linked list\r\n85 15 4 20 \r\nReversed Linked list \r\n20 4 15 85<\/pre>\n
Time Complexity:<\/strong> O(n)
\nSpace Complexity:<\/strong> O(1)<\/p>\n[ad type=”banner”]\n
Recursive Method:<\/strong><\/p>\n
   1) Divide the list in two parts - first node and rest of the linked list.\r\n   2) Call reverse for the rest of the linked list.\r\n   3) Link rest to first.\r\n   4) Fix head pointer<\/pre>\n<\/div>\n
\"Write<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
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;              }<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(n)
\nSpace Complexity:<\/strong> O(1)<\/p>\n[ad type=”banner”]\n
C++ Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ A simple and tail recursive C++ program to reverse\/\/ a linked list#include<bits\/stdc++.h>using namespace std; struct node{    int data;    struct node *next;}; void reverseUtil(node *curr, node *prev, node **head); \/\/ This function mainly calls reverseUtil()\/\/ with prev as NULLvoid reverse(node **head){    if (!head)        return;    reverseUtil(*head, NULL, head);} \/\/ A simple and tail recursive function to reverse\/\/ a linked list.  prev is passed as NULL initially.void reverseUtil(node *curr, node *prev, node **head){    \/* If last node mark it head*\/    if (!curr->next)    {        *head = curr;         \/* Update next to prev node *\/        curr->next = prev;        return;    }     \/* Save curr->next node for recursive call *\/    node *next = curr->next;     \/* and update next ..*\/    curr->next = prev;     reverseUtil(next, curr, head);} \/\/ A utility function to create a new nodenode *newNode(int key){    node *temp = new node;    temp->data = key;    temp->next = NULL;    return temp;} \/\/ A utility function to print a linked listvoid printlist(node *head){    while(head != NULL)    {        cout << head->data << " ";        head = head->next;    }    cout << endl;} \/\/ Driver program to test above functionsint main(){    node *head1 = newNode(1);    head1->next = newNode(2);    head1->next->next = newNode(3);    head1->next->next->next = newNode(4);    head1->next->next->next->next = newNode(5);    head1->next->next->next->next->next = newNode(6);    head1->next->next->next->next->next->next = newNode(7);    head1->next->next->next->next->next->next->next = newNode(8);    cout << "Given linked list\\n";    printlist(head1);    reverse(&head1);    cout << "\\nReversed linked list\\n";    printlist(head1);    return 0;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/p>\n
Given linked list\r\n1 2 3 4 5 6 7 8\r\n\r\nReversed linked list\r\n8 7 6 5 4 3 2 1<\/pre>\n","protected":false},"excerpt":{"rendered":"
C Algorithm – Write a function to reverse a linked list – Linked List – Given pointer to the head node of a linked list, the task is to reverse<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,79476,79478],"tags":[80299,81347,81346,81349,80298,80296,81345,80300,81342,81348,80297,81344,81343],"class_list":["post-27260","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-linked-list","category-singly-linked-list","tag-algorithm-to-reverse-a-linked-list-in-data-structure","tag-how-to-reverse-a-linked-list-c","tag-how-to-reverse-a-linked-list-in-c","tag-how-to-reverse-a-linked-list-python","tag-reverse-a-linked-list-algorithm","tag-reverse-a-linked-list-c","tag-reverse-a-linked-list-in-groups-of-size-k","tag-reverse-a-linked-list-recursively-c","tag-reverse-a-linked-list-using-recursion","tag-reverse-doubly-linked-list-java","tag-reverse-linked-list-recursive-java","tag-reversing-a-linked-list-in-c-with-explanation","tag-reversing-a-linked-list-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27260","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27260"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27260\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27260"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27260"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}