Question: Write a C program to reverse a singly linked list.
Find below both recursive and iterative functions to reverse a link list. Both functions have same time complexity. Recursive function is called as head = list_reverse1(head, NULL), it returns a pointer to the head of the new list. Iterative function call is self explanatory.
Time Complexity: O(n)
/* recursive */
list *list_reverse_recursive(list *curr, list *prev)
{
list *head = NULL;
if (curr == NULL) {
return prev;
}
head = list_reverse_recursive(curr->next, curr);
curr->next = prev;
return head;
}
/* iterative */
void list_reverse_iterative(list **head)
{
list *prev = NULL, *curr = *head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
Find below both recursive and iterative functions to reverse a link list. Both functions have same time complexity. Recursive function is called as head = list_reverse1(head, NULL), it returns a pointer to the head of the new list. Iterative function call is self explanatory.
Time Complexity: O(n)
/* recursive */
list *list_reverse_recursive(list *curr, list *prev)
{
list *head = NULL;
if (curr == NULL) {
return prev;
}
head = list_reverse_recursive(curr->next, curr);
curr->next = prev;
return head;
}
/* iterative */
void list_reverse_iterative(list **head)
{
list *prev = NULL, *curr = *head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
Another Better Version of Singly Linked List
ReplyDeletevery good one. also see this:
ReplyDeletereverse linked list recursive