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",c开发者_StackOverflow社区urrent->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?

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;
       }

  }

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.

You forgot to update the next member of the first item on the linked list. Add parent->next = NULL; before the recursion call.

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;
}

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

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;

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.

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;
}

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

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;
    }
     
} '