Last active
November 27, 2015 03:50
-
-
Save jitsceait/b275fc9599f82feb2ef4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
typedef struct Node { | |
int data; | |
struct Node * next; | |
} Node; | |
Node * create_node(int val){ | |
Node * temp = (Node *)malloc(sizeof(Node)); | |
if(temp){ | |
temp->data = val; | |
temp->next = NULL; | |
} | |
return temp; | |
} | |
/* This function inserts node at the head of linked list */ | |
void push(Node **headRef, int data){ | |
Node * new_node = (Node *)malloc(sizeof(Node)); | |
new_node->data = data; | |
new_node->next = *headRef; | |
*headRef = new_node; | |
} | |
void print_list(Node * head){ | |
while(head){ | |
printf("%d->", head->data); | |
head = head->next; | |
} | |
printf("Null"); | |
} | |
Node * reverse_linked_list_rec(Node * head){ | |
//If there are no node in linked list, just return | |
if(!head) return head; | |
//There is only one node in list, return that node. | |
if(!(head->next)) return head; | |
/* | |
Above two conditions can be written as | |
if(!head || !(head->next)) return head; | |
*/ | |
/* | |
In this step, we are removing the first node, i.e head and | |
reverse the remaining list | |
Also, when fist time return from recusive call, it will be the last | |
node of linked list and that will be the head of reversed list. | |
We will successively return the same head to upper calling function. | |
*/ | |
Node * new_head = reverse_linked_list(head->next); | |
/* | |
Removed node, here head node should be added to end of list. | |
It can be seen that last node in reversed list will next node of head. | |
Keep in mind we are relying on the fact that removed_node->next is not | |
null in any case.In implementation take care to this fact. If this is | |
violated, we may end up getting null pointer exception | |
*/ | |
head->next->next = head; | |
head->next = NULL; | |
return new_head; | |
} | |
int main(void) { | |
Node * head = NULL; | |
push(&head, 3); | |
push(&head, 4); | |
push(&head, 5); | |
push(&head, 6); | |
push(&head, 7); | |
printf("\n Original list :"); | |
print_list(head); | |
head = reverse_linked_list_rec(head); | |
printf("\n Reverse list :"); | |
print_list(head); | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment