Reputation: 3021
reversing linked list
I am trying to reverse a linked list using recursion and wrote the following code for it. The list is start of the list at the beginning.
node *reverse_list_recursive(node *list)
{
node *parent = list;
node *current = list->next;
if(current == NULL)
return parent;
else
{
current = reverse_list_recursive(current);
current->next = parent;
printf("\n %d %d \n",current->value,parent->value);
return parent;
}
}
I could see that all the links are getting reversed. However when I try to display, I get an infinite prints of the numbers. I suspect an error when I am trying to reverse the link for the first number originally in the list.
What am I doing wrong?
Upvotes: 7
Views: 2022
Answers (10)
Reputation: 1
Different code is below :
'
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
struct Node {
int data;
struct Node* next;
};
typedef struct Node node;
node* dogrusıralama(node* r)
{
for (int i = 0; i < 6; i++)
{
printf("%d", r->data);
r = r->next;
printf("\n");
}
}
node *terssıralama(node* r)
{
node* iter;
iter = r;
node* temp;
temp = r;
node* temp2;
temp2 = r;
int a = 4;
for (int k = 0; k < 5; k++)
{
temp2 = temp2->next;
}
for (int j = 0; j < 5; j++)
{
int i = a;
for (; i > 0; i--)
{
temp = temp->next;
}
a--;
iter = temp;
iter->next->next = iter ;
temp = r;
}
temp->next = NULL;
return temp2;
}
int main() {
node* dugum;
node* dugum2;
node* dugum3;
node* dugum4;
dugum = (node*)malloc(sizeof(node*));
dugum2 = dugum;
for (int i = 0; i < 5; i++)
{
dugum2->next = NULL;
dugum2->next = (node*)malloc(sizeof(node*));
dugum2->data = i;
dugum2 = dugum2->next;
}
dugum4 = dugum;
dogrusıralama(dugum);
dugum3 = terssıralama(dugum);
for (int i = 0; i < 6; i++)
{
printf("\n");
printf("%d", dugum3->data);
dugum3 = dugum3->next;
}
} '
Upvotes: 0
Reputation: 17
Here goes recursive code to reverse a linked list.
list * reverse(list * head)
{
if( head == NULL || head -> link == NULL )
return head;
list *node = reverse( head- > link );
head -> link -> link = head;
head -> link = NULL;
return node;
}
Upvotes: 1
Reputation: 5947
Severl versions above are not working as OP wanted, so here is my recursive version tested fine:
node * reverseRecursive(node *p,node **head)
{
if(p->next == NULL)
{
*head = p;
return p;
}
node *before;
before = reverseRecursive(p->next,head);
before->next = p;
p->next = NULL;
return p;
}
//call from main
node*head;
//adding value
//assuming now head is now 1->2->3->4->NULL
node* newHead;
reverseRecursive(head,&newHead);
//now now newHead is now 4->3->2->1->NULL
Upvotes: 0
Reputation:
Suppose I have a linked list:
---------- ---------- ---------- ----------
| 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL
---------- ---------- ---------- ----------
Your code converts it to:
---------------------- ----------------------
| | | |
v | v |
---------- ---------- ---------- ----------
| 1 | |--->| 2 | | | 3 | | | 4 | |
---------- ---------- ---------- ----------
^ |
| |
----------------------
Notice that the first element still points back to 2.
If you add the line parent->next = NULL after the first two, you will get:
---------------------- ----------------------
| | | |
v | v |
---------- ---------- ---------- ----------
NULL<---| 1 | | | 2 | | | 3 | | | 4 | |
---------- ---------- ---------- ----------
^ |
| |
----------------------
which is in fact the correct structure.
The complete code is: (You only need to print the current value for each recursive call)
node *reverse_list_recursive(node *list)
{
node *parent = list;
node *current = list->next;
if(current == NULL)
return parent;
else
{
current = reverse_list_recursive(current);
parent->next = NULL;
current->next = parent;
printf("\n %d \n",current->value);
return parent;
}
}
Upvotes: 5
Reputation: 15892
I don't see the benefit of recursion here, iteration will work just as well. It's been forever since I've written C (and no easy way to test the following for syntax errors... or cringe core dumps, but you get the idea).
node *reversed_list(node *list) {
node *fwd=list;//Purely for readability
node *last=null;
node *next=null;
node *rev=null;
do {
//Cache next
next=fwd->next;
//Set current
rev=fwd;
//Reset next to point back
rev->next=last;
//Update last
last=fwd;
//Forward ptr;
fwd=next;
} while (fwd!=null);
return rev;
}
Pretty sure your *list is useless after you've called this since it's now pointing to last element of the list which has ->next=null, could just update that instead of returning the pointer.
Update (for recursive solution)
As others have said, your new tail is messed up (points back at the last element, but should point to null)... and you don't return the correct head, you return the second element. Consider the list a->b->null with your algorithm:
p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a return a; //a->b, b->a, a returned //But what you wanted is a->null, b->a, and b returned
The following updated code will fix:
node *reverse_list_recursive(node *list)
{
node *parent = list;
node *current = list->next;
if(current == NULL)
return parent;
else
{
current = reverse_list_recursive(current);
current->next = parent;
parent->next=null; //Fix tail
printf("\n %d %d \n",current->value,parent->value);
return current; //Fix head
}
}
With list a->b->null:
p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a p->next=null //a->null return b; // b->a->null
Upvotes: 2
Reputation: 41749
You need to set the new tail (i.e the old head)'s next pointer to NULL
EDIT: Here's a recursive version
node *reverse_list_recursive(node *list)
{
node *parent = list;
node *child = list->next;
node *new_head;
if (child == NULL)
return parent ; /* new head */
new_head = reverse_list_recursive(child)
child->next = parent; /* Old parent is the new child of the old child when reversed */
parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */
return new_head;
}
Upvotes: 2
Reputation: 455030
Some problems I could see:
- You need to make the next pointer of the new last node NULL.
- You existing function will blow if I pass NULL to it initially.
Upvotes: 1
Reputation: 35594
After the line current = reverse_list_recursive(current); you are storing the new list head in current, so current->next = parent; is wrong. New current is the new list head, but you need to access the new list tail, i.e., the OLD current:
node* newhead = reverse_list_recursive(current);
current->next = parent;
printf("\n %d %d \n",current->value,parent->value);
return newhead;
Upvotes: 1
Reputation: 34704
You forgot to update the next member of the first item on the linked list. Add parent->next = NULL; before the recursion call.
Upvotes: 2
Reputation: 5780
When you reach the end of the list, you return the last node. That last node's next value then gets assigned to itself, hence you'd create an inconsistency. If current is NULL, return NULL instead and simply disregard the rest of the code if the return is NULL.
Upvotes: 2
Related Questions
- Reversing a doubly linked list in C
- Reverse linked list C
- Store reverse of given linked list into another linked list
- C - Linked list - Linked in the reversed way
- Reversing Linked List with Function
- Reverse double linked list
- linked list reverse without temp
- Reversing a Singly Linked List
- Reversing a Linked List in C
- Reversing a linked list that has a Loop