[ Home  |  FAQ-Related Q&As  |  General Q&As  |  Answered Questions ]

    Search the Q&A Archives

...most efficient method to reverse a linked list ?...

<< Back to: comp.lang.c FAQ list Table of Contents

Question by Shashikiran
Submitted on 12/10/2003
Related FAQ: comp.lang.c FAQ list Table of Contents
Rating: Rate this question: Vote
What is the most efficient method to reverse a linked list ?


Answer by Sudhakar
Submitted on 1/2/2004
Rating:  Rate this answer: Vote
swap first elment and last element.
Then second element with second element from last and proceed like tht..

 

Answer by ricki
Submitted on 2/17/2004
Rating:  Rate this answer: Vote
Recursive method of reversing the linked list is the best bet !

 

Answer by raghu
Submitted on 3/2/2004
Rating:  Rate this answer: Vote
Sudhakar,
singly linked list??

if its a doubly linked list then just swap the prev and next pointers for each node and make the current tail as head.
else ricki'sanswer would be fine.

 

Answer by spongman
Submitted on 3/5/2004
Rating:  Rate this answer: Vote
You don't need recursion to reverse a singly-linked list.

Node *Reverse (Node *p)
{
   Node *pr = NULL;
   while (p != NULL)
   {
      Node *tmp = p->next;
      p->next = pr;
      pr = p;
      p = tmp;
   }
   return pr;
}

 

Answer by rana
Submitted on 3/9/2004
Rating:  Rate this answer: Vote
can we reverse a singly linked list using just one variable ?

 

Answer by Peter
Submitted on 3/21/2004
Rating:  Rate this answer: Vote
Yes, you can.
You have to keep the pointer to the first element in a variable, go to the second and swap the values, then go to the third and keep doing this.
Do you know how to swap values without a temporary variable?
a = 2;
b = 3;
a = a + b; (now a is 5)
b = a - b; (now b is 2)
a = a - b; (now a is 3)
pplupo@hotpop.com

 

Answer by DJ
Submitted on 3/25/2004
Rating:  Rate this answer: Vote
Can someone show me the code for linked list reversal using recursion when the argument passed is only the head.

thanx

 

Answer by bijusown
Submitted on 4/5/2004
Rating:  Rate this answer: Vote
Node *reverseList(Node *current, Node *parent)
{
        Node *revHead;
   if(current == null)
      revHead = parent;
   else
   {
      revHead = reverseList(current->next,current);
      current->next = parent;      
   }
   return revHead;
}

Initial method call should be

head = reverseList(head,NULL)


 

Answer by murtuzabookwala
Submitted on 4/22/2004
Rating:  Rate this answer: Vote
Unfortunately uses global variable 'tail'
which would later point to the reversed list

list *tail;

list *reverse (list *node)
{
  if (node->next == NULL)
  {
    tail = node;
    return;
  }
  else
  {
    reverse (node->next);
    node->next->next = node;
    node->next = NULL;
  }
}

Called as: reverse(head);

 

Answer by bob
Submitted on 4/24/2004
Rating:  Rate this answer: Vote
Recursion is noones friend

 

Answer by mozzis
Submitted on 4/30/2004
Rating:  Rate this answer: Vote
bijusown's answer destroys the list without doing anything useful. For instance, the first time through the loop, the head's next pointer is replaced with NULL. Oops - now you've orphaned the rest of the list.


 

Answer by nelly
Submitted on 5/5/2004
Rating: Not yet rated Rate this answer: Vote
mozzis, actually, that's not true. In bijusown'ssolution, the initial head's next pointer is only set to null after the rest of the list has been reversed. Hence, the old head now becomes the new tail while the old head->next is now pointing to head.

 

Answer by nelly
Submitted on 5/5/2004
Rating:  Rate this answer: Vote
mozzis, actually, that's not true. In bijusown's solution, the initial head's next pointer is only set to null after the rest of the list has been reversed. Hence, the old head now becomes the new tail while the old head->next is now pointing to head.

 

Answer by hanpa00
Submitted on 5/10/2004
Rating:  Rate this answer: Vote
Another recursive function that can reverse a linked list.

To call the function:
  newHead = reverse(head);

struct Node *reverse(Node *curp)
{
  static struct Node *head = curp;
  static struct Node *revHead = NULL;
  if (curp == NULL)
    return NULL;
  if (curp->next == NULL)
    revHead = curp;
  else
    reverse(curp->next)->next = curp;
  if (curp == head) {
    curp->next = NULL;
    return revHead;
  }
  else
    return curp;
}

 

Answer by am
Submitted on 5/11/2004
Rating:  Rate this answer: Vote
Is there a particular reason why someone would want to implement this recursively, as opposed to the iterative solution? Just wondering... Unless the recursive case is for interviewing purposes to show familiarity with the concept?

 

Answer by al
Submitted on 5/20/2004
Rating:  Rate this answer: Vote
Am, what else is recursion for?

 

Answer by sdfsd
Submitted on 6/23/2004
Rating:  Rate this answer: Vote
sdfsdfsdf

 

Answer by ramuguda
Submitted on 6/27/2004
Rating:  Rate this answer: Vote
node *reverse(node *head)
{
node *temp;

if(head->next)
{
   temp=reverse(head->next);
   head>next->next=head;
   head->next=NULL;
}
else
  temp=head;

return temp;
}

call as: head=reverse(head);

 

Answer by basha nit Warangal
Submitted on 8/20/2004
Rating: Not yet rated Rate this answer: Vote
struct node * reverse(struct node *n)
{
   if (n->next==NULL)
    {
        return n;
    }
    return (reverse(first,n->next)->next=n);
}

here function call is like
   first = reverse(first)where first is a pointer to starting node.

 

Answer by darathi
Submitted on 8/25/2004
Rating: Not yet rated Rate this answer: Vote
we can reverse the single linked list using stack or recursive. which one is best in these two

 

Answer by Kest
Submitted on 9/10/2004
Rating: Not yet rated Rate this answer: Vote
The simplest recursive solution IMHO is:

Node * reverse(Node * cur, Node * par) {
    Node * temp = cur->next;
    cur->next = par;
    if (temp == NULL)
        return cur;
    else
        return reverse(temp,cur);
}

 

Answer by Shantanu
Submitted on 9/16/2004
Rating: Not yet rated Rate this answer: Vote
Suppose you already have the head and tail of the list.

Node*    Reverse(  )
{
   Node * NewHead = Head;
   Node * AuxiliaryTail = Tail;

   While ( NewHead != AuxiliaryTail )
   {
   Node* Tmp = NewHead ;
   NewHead = NewHead->next ;
   Tmp->next = AuxiliaryTail->next;
   AuxiliaryTail->next = Tmp;
   }

        return  NewHead;
}

 

Answer by gaur
Submitted on 10/5/2004
Rating: Not yet rated Rate this answer: Vote
bijusown'ssolution is not correct. While reversing the linked list only the last link in the list is returned and the rest of the linked list is isolated

 

Answer by Sandeep.D.M
Submitted on 11/20/2004
Rating: Not yet rated Rate this answer: Vote
void reverse(Node *First)
{
Node *Sec,*Thir; //Create 2nd &3rd nextnode  

Sec=First->next;
First->next=NULL;

while(Thir != NULL)
    {
    Thir=Sec->next; //get the seconf & third
    s->next=First;  //node address
    First=Sec;    
    Sec=Thir;
    Thir=Thir->next;
    }
Sec->next=First;
return (Sec); //Return the first node
}




 

Answer by basha
Submitted on 12/22/2004
Rating: Not yet rated Rate this answer: Vote
struct node * reverse(struct node **first,struct node *h)
{
  if (h->next == NULL)
   {
       *first=h;
        return h;
    }
   else
     return(reverse(h->next)->next=h);
}

suppose
struct node
{
int data;
struct node *next;
}*first;
Here first is the pointer to starting node of the single linked list.
Function call should be

reverse(&first,first);

 

Answer by BASHA
Submitted on 12/23/2004
Rating: Not yet rated Rate this answer: Vote
REVERSING A LINKED LIST

struct node * reverse(struct node **first, struct node *h)
{
  if (h && h->next ==NULL)
  {
    *first=h;
     return h;
  }
  else if (h)
return ( reverse(&first,h->next)->next = h);
return NULL;
}

NODE STRUCTURE IS
struct node
{
  int data;
  struct node *next;
}*first=NULL:


HERE first IS A POINTER TO STARTING NODE OF THE SINGLE LINKED LIST.

CALL TO THIS FUNCTION IS

reverse(&first,first);

 

Answer by wkc
Submitted on 1/9/2005
Rating: Not yet rated Rate this answer: Vote
the "if" should be "if (head && head->next), in case the head parameter is NULL.
but otherwise the solution is elegant.

 

Answer by Nealo
Submitted on 2/2/2005
Rating: Not yet rated Rate this answer: Vote
Recursion is only good for helping programmers think.  Anything done with recursion can be done more efficiently without it, because you don't have to waste time calling functions.  For recursively reversing a list, this would be a function call for each element.  But programming ease has become a high priority now that processing power is fairly cheap.

 

Answer by Nealo
Submitted on 2/2/2005
Rating: Not yet rated Rate this answer: Vote
Also, for swapping two values without a temp variable, using binary XOR may be a better idea, because you don't have to worry about overflow.  Though I don't remember if you can XOR in C, you should probably watch out for overflow.

 

Answer by Al
Submitted on 2/16/2005
Rating: Not yet rated Rate this answer: Vote
void reverse(list *head) {
    list *temp1, *temp2;
    if (head == null)
        return;
    
    temp1 = head->next;
    head->next = null;
    
    while(temp1 != null) {
   temp2 = temp1->next;
   temp1-> next = head;
   head = temp1;
   temp1 = temp2;
    }
}

 

Answer by Krishna Nadh
Submitted on 2/18/2005
Rating: Not yet rated Rate this answer: Vote
// Reverses the given linked list by changing its .next pointers and
// its head pointer. Takes a pointer (reference) to the head pointer.
void Reverse(struct node** headRef) {
if (*headRef != NULL) { // special case: skip the empty list
/*
Plan for this loop: move three pointers: front, middle, back
down the list in order. Middle is the main pointer running
down the list. Front leads it and Back trails it.
For each step, reverse the middle pointer and then advance all
three to get the next node.
*/
struct node* middle = *headRef; // the main pointer
struct node* front = middle->next; // the two other pointers (NULL ok)
struct node* back = NULL;
while (1) {
middle->next = back; // fix the middle node
if (front == NULL) break; // test if done
34
back = middle; // advance the three pointers
middle = front;
front = front->next;
}
*headRef = middle; // fix the head pointer to point to the new front
}
}

 

Answer by Krishna Nadh
Submitted on 2/18/2005
Rating: Not yet rated Rate this answer: Vote
// Reverses the given linked list by changing its .next pointers and
// its head pointer. Takes a pointer (reference) to the head pointer.
void Reverse(struct node** headRef) {
if (*headRef != NULL) { // special case: skip the empty list
/*
Plan for this loop: move three pointers: front, middle, back
down the list in order. Middle is the main pointer running
down the list. Front leads it and Back trails it.
For each step, reverse the middle pointer and then advance all
three to get the next node.
*/
struct node* middle = *headRef; // the main pointer
struct node* front = middle->next; // the two other pointers (NULL ok)
struct node* back = NULL;
while (1) {
middle->next = back; // fix the middle node
if (front == NULL) break; // test if done
34
back = middle; // advance the three pointers
middle = front;
front = front->next;
}
*headRef = middle; // fix the head pointer to point to the new front
}
}

 

Answer by IceBryce
Submitted on 2/24/2005
Rating: Not yet rated Rate this answer: Vote
  public void reverse()
  {

    Node curr = top;

    if(top!=null && top.next != null)
   {
      top = top.next;
      reverse();

      curr.next.next=curr;
      curr.next=null;
     }


  } // end method reverse

 

Answer by Kartik
Submitted on 2/25/2005
Rating: Not yet rated Rate this answer: Vote
And the iterative counterpart:

node* reverse(node* now)
{
   node* temp;
   node* tobe = NULL;
   while(temp != null)
   {
      temp = now->next;
      now->next = tobe;
      tobe = now;
      now = temp;
   }
   return now;
}

node* new_start = reverse(orig_start);

 

Answer by Sohel
Submitted on 2/26/2005
Rating: Not yet rated Rate this answer: Vote
void reverse(node **s)
{
node *back;
node *front;
node *a=*s;
int temp;

if(a==NULL) return;
if(a->next==NULL) return;

front = a;
back=NULL;
while (a != NULL)
{
   front=a->next;
   a->next=back;
   back=a;
   a=front;
}//while
*s = back;

}

 

Answer by priya
Submitted on 2/28/2005
Rating: Not yet rated Rate this answer: Vote
hi

please help me to write this code .
write a code to print out  the intersection of two single linked lists in a (decending order)ie after getting the intersection elements you have to  sort it in a descending order and then print it out.



 

Answer by priya
Submitted on 2/28/2005
Rating: Not yet rated Rate this answer: Vote
hi

write a code to print out  the intersection of two single linked lists in a reverse order.


 

Answer by navneet
Submitted on 3/20/2005
Rating: Not yet rated Rate this answer: Vote
//
// iterative version
//
Node* ReverseList( Node ** List )   
{

   Node *temp1 = *List;
   Node * temp2 = NULL;
   Node * temp3 = NULL;

   while ( temp1 )
   {
      *List = temp1; //set the head to last node      
temp2= temp1->pNext; // save the next ptr in temp2
      temp1->pNext = temp3; // change next to privous
      temp3 = temp1;
      temp1 = temp2;
   }

   return *List;
}

 

Answer by AshTray
Submitted on 4/4/2005
Rating: Not yet rated Rate this answer: Vote
This piece of code works correctly and doesn't assume any headnodes.

¨Ustruct node* recRev(struct node *head)
¨U{
¨Ustruct node *temp;
¨U
¨U  if(head -> next)
¨U  {
¨U    temp = recRev(head -> next);
¨U    head->next->next = head;
¨U    head->next=NULL;
¨U  }
¨U  else
¨U        temp = head;
¨Ureturn temp;
¨U}

 

Answer by naik
Submitted on 4/7/2005
Rating: Not yet rated Rate this answer: Vote
void reverse(struct doublell **dll)
{
   struct doublell *a,*b,*c;

   a = *dll;

   c=NULL;

   while(a!=NULL)
   {
      b=c;
      c=a;
      a=a->link;
      c->link=b;
   }

   *dll = c;
}

 

Answer by available
Submitted on 4/22/2005
Rating: Not yet rated Rate this answer: Vote
Recursions are beautiful and simple. However, in real world, the iterative algorithm is more robust. The simple reason is the fact that the stack in most systems has a limited size. Therefore, depending how deep your recursive function is called or how long the linked list is, you may run out of stack and ... Well, you will get a late night call to go fix it, :-(.

 

Answer by Max
Submitted on 5/1/2005
Rating: Not yet rated Rate this answer: Vote
void
reverse(struct node **head)
{
  if((*head == NULL)||((*head)->next==NULL))
    return;
  struct node *first = *head;
  struct node *rest = first->next;
  reverse(&rest);
  first->next->next = first;
  first->next = NULL;
  *head = rest;
}

 

Answer by ub
Submitted on 5/4/2005
Rating: Not yet rated Rate this answer: Vote
This is (almost) the same as the solution by ramuguda - except that you don't need a temp

struct node * recreverse (struct node* n) {
   if (!n->nextnode)
      return n;
   else {
      recreverse(n->nextnode);
      n->nextnode->nextnode = n;
      n->nextnode = NULL;
     
   }
}

 

Answer by Lolla
Submitted on 5/5/2005
Rating: Not yet rated Rate this answer: Vote
node* Reverse_List(node* head)
{
  if((head == NULL) || (head->next) == NULL))
  return head;
  else{
    node* p1, *p2, *tmp;
    p1 = h; p2 = p1->next; temp = p2;   p1->next = NULL;
    while(p2->next != NULL){
      temp = p2;
      p2->next = p1->next;
      p1 = tmp;
      p2 = tmp->next;
      }
    h = p2;
    return h;
    }
  }
}

 

Answer by bhandari
Submitted on 5/8/2005
Rating: Not yet rated Rate this answer: Vote
I am maintaining a global start pointer which points to the first node.
How to reverse the list. I am not passing any element to the reverse() function.

 

Answer by kissie
Submitted on 5/23/2005
Rating: Not yet rated Rate this answer: Vote
node *reversenode(node * start)
{
   node *temp,*front = start;
   if(front->next)
   {
      temp = reversenode(front->next);
      temp->next = front;
      temp = front;
      temp->next =NULL;
   }
   else
      temp = front;
   return temp;

}

 

Answer by sandhya
Submitted on 5/27/2005
Rating: Not yet rated Rate this answer: Vote
please can any one show me a c program to create  a single linked list?
thanks

 

Answer by quirrex
Submitted on 6/7/2005
Rating: Not yet rated Rate this answer: Vote
Peter, could you please show me the code of how do you reverse the list with just one variable?
thanx

 

Answer by Danny
Submitted on 6/11/2005
Rating: Not yet rated Rate this answer: Vote
ramuguda, ur solution almost always returns NULL (except that the list contains only 1 element), which is incorrect.

 

Answer by sreenithk
Submitted on 6/28/2005
Rating: Not yet rated Rate this answer: Vote
another way to reverse linklist recursively. linklist is the class and head a member of that class which holds the pointer to first link of the linklist a.k.a head.

void linklist::reverse(linklist *current, linklist *parent)
{
   if(current->next == NULL)
      head = current;
   else
      reverse(current->next, current);
   current->next = parent;   
}

 

Answer by RakeshPawar
Submitted on 7/20/2005
Rating: Not yet rated Rate this answer: Vote
Recursive Method to reverse a singly Linked List:  ---
Node *Reverse(Node *ptr)
{
   if(ptr->next==NULL)
     return ptr;
   temp=Reverse(ptr->next)
   temp>next=ptr;
   return ptr;
}

 

Answer by Soham
Submitted on 7/31/2005
Rating: Not yet rated Rate this answer: Vote
Node* Rev(Node *pHead)
{
   Node *temp = NULL;

   if (pHead && pHead->pNext) //short circuit
      {temp = Rev(pHead->pNext);}
   else
      {return pHead;}

   pHead->pNext->pNext = pHead;
   pHead->pNext = NULL;

   return temp;
}

 

Answer by Soham
Submitted on 7/31/2005
Rating: Not yet rated Rate this answer: Vote
Iterative solution:


void RevIter(Node **ppHead)
{
   Node *pF = NULL, *pS = NULL, *pSave = NULL;
   
   if(!ppHead || !*ppHead)
      return;

   pF = *ppHead;
   pS = pF->pNext;
   pF->pNext = NULL; //Last node

   while(pS)
   {
      pSave = pS->pNext;
      pS->pNext = pF;

      pF = pS;
      pS = pSave;
   }

   *ppHead = pF;
}

 

Answer by ram
Submitted on 8/3/2005
Rating: Not yet rated Rate this answer: Vote
how dos o.s can be installed

 

Answer by trilogy
Submitted on 8/22/2005
Rating: Not yet rated Rate this answer: Vote
Gr8 answer guys , but the fundamental concept is the same for everyones reverse function, cheers

 

Answer by RAMASWAMY BM
Submitted on 10/8/2005
Rating: Not yet rated Rate this answer: Vote
reverse()
{
p=head;
q=p;
p->next=NULL;
while(q!=NULL)
{
r=q->next;
p->next=q;
p=q;
q=r;
}
head=p;
}

 

Answer by joan
Submitted on 10/25/2005
Rating: Not yet rated Rate this answer: Vote
void reverse(node *now)
{
head = now->next;
if (now->next->next != NULL )
reverse(now->next);
if ( now->next->next == NULL ){
now->next->next = node;
now->next = NULL;
};

};

 

Answer by Bodaddy
Submitted on 11/10/2005
Rating: Not yet rated Rate this answer: Vote
Here's and iterative approach

ListItem * ReverseList(ListItem * list)
{
//Makes use of two pointers and the
//passed in list pointer to reverse
//the singly linked list
if(list)
{
ListItem * temp0 = list;
ListItem * temp1 = NULL;
while(list->next)
{
list = list->next;
temp0->next = temp1;
temp1=temp0;
temp0=list;
}
//we are at the tail node so set
//the list pointer's next to temp1
list->next = temp1;
}
return list;
}

Call as head=ReverseList(head)

 

Answer by asdf
Submitted on 11/16/2005
Rating: Not yet rated Rate this answer: Vote
poon kha lae :)

 

Answer by whats wrong with
Submitted on 11/25/2005
Rating: Not yet rated Rate this answer: Vote
public void reverse ()
    {
        Node a = list;
        Node b = a.next;
        a.next = null;
               Node c = b.next;
        do
        {
            b.next = a;
            c.next = b;
            a = b;
            b = c;
            c = c.next;

        }
        while (a != null);
        list = a;
    }

 

Answer by Anupam
Submitted on 11/30/2005
Rating: Not yet rated Rate this answer: Vote
What is better ? in terms of efficieny.. iterative method or recursive method?

 

Answer by Santosh P K
Submitted on 12/20/2005
Rating: Not yet rated Rate this answer: Vote
struct node* reverse(struct node *n1, struct node *n1Parent)
{

    struct node *temp;

    if (n1 == NULL)
    {
        return n1Parent;
    }
    temp = n1->next;
    n1->next = n1Parent;
    return  reverse (temp,n1);

}


function should be called as reverse (n1, NULL);

 

Answer by Santosh P K
Submitted on 12/20/2005
Rating: Not yet rated Rate this answer: Vote
struct node *reverse (struct node *node)
{
   struct node *node1;
  if (node->next == NULL)
  {
    return node;
  }
  else
  {
    node1 = reverse1 (node->next);
    node1->next = node;
    node->next = NULL;
    return node;
  }
}

 

Answer by xtele
Submitted on 12/22/2005
Rating: Not yet rated Rate this answer: Vote
simplest one.

Node* recursive_reverse(Node *node)
{
  if (!node)
    return NULL;

  if (!node->next) {
    recursive_reverse(node->next);
    node->next->next = node;
  }
  return node;
}

 

Answer by palash
Submitted on 12/28/2005
Rating: Not yet rated Rate this answer: Vote
best efficient method is:

NODE reverse_list(NODE first)
{
NODE temp,cur;
cur=NULL;
while(first!=NULL)
{
temp=first;
first=first->link;
temp->link=cur;
cur=temp;
}
return cur;
}

 

Answer by Foobar
Submitted on 1/22/2006
Rating: Not yet rated Rate this answer: Vote
void RecursiveReverse(Node ** pnHead, Node * pnCurr, Node * pnPrev)
{
   assert(pnHead && *pnHead);

   if (!pnCurr)
   {
      (*pnHead)->pnNxt = NULL;
      *pnHead = pnPrev;      
      return;
   }

   pnPrev = pnCurr;
   pnCurr = pnCurr->pnNxt;
         
   RecursiveReverse(pnHead, pnCurr, pnPrev);
   
   if (pnCurr)
      pnCurr->pnNxt = pnPrev;      
}

 

Answer by AshwathKumar_Punacha
Submitted on 1/30/2006
Rating: Not yet rated Rate this answer: Vote
The basic idea is to use three pointers and walk them down the list. Within the list, the 'forward' pointer is moved down one item. The 'middle' pointer it left where it is, one behind the 'forward' pointer, while the 'back' pointer is left one behind the 'middle' pointer. The 'next' field of the 'middle' pointer's object is set to point at the 'back' pointer, thus reversing the direction of the link in the middle. At this point, the 'back' pointer is moved up one by assigning it to point at 'middle'sobject, and middle is moved up one by assigning it to point at 'forward'sobject, which sets everything up for the next iteration. With that in mind, it's only necessary to take care of the special cases that arise at the beginning and end of the linked list.

 

Answer by asdf
Submitted on 2/5/2006
Rating: Not yet rated Rate this answer: Vote
who cares

 

Answer by xspark86
Submitted on 2/15/2006
Rating: Not yet rated Rate this answer: Vote
WONDERFUL ANSWER BY ramuguda.

Can anyone, though, explain how he developed this code? I have no idea. Are there mathematical/analytical way of approach to develop the above code?

 

Answer by MOHIT KHURANA
Submitted on 2/26/2006
Rating: Not yet rated Rate this answer: Vote
code for linked list reversal using recursion when the argument passed is only the head.
--------------------------------------------
void reversedisp(node *p)
{
   if(p==0)
     return;
   else
    {
      return(reversedisp(p->next);
      cout<<p->info;
    }
   return;
}

CALL AS:reversedisp(head)

 

Answer by Ani
Submitted on 3/11/2006
Rating: Not yet rated Rate this answer: Vote
You will need to pass head as head = reverse(&head) and receive it in the function as reverse(node **head) so as to retain the changes. Also temp = head should always happen in both cases (head -> next is null or not) and should be put outside of else. This will make sure that the head returned to the main program is the right head.

 

Answer by asdasd
Submitted on 4/4/2006
Rating: Not yet rated Rate this answer: Vote
<SPAN ID='ss' style='display:none'/>
sdsd

 

Answer by Aditi
Submitted on 4/5/2006
Rating: Not yet rated Rate this answer: Vote
can we perform doubly linked list with the help of singly linked list ? if yes then how

 

Answer by libzee
Submitted on 4/19/2006
Rating: Not yet rated Rate this answer: Vote
void rev()

        {
                      int stack[50],i=0;
                 ptr=head->link;
                     if(ptr!=NULL)
                      {
                              while(ptr!=NULL)
                              {
    
                                      stack[i]=ptr->data;
                                      i++;
                                      ptr=ptr->link;
                             }
              i--;
                              ptr=head->link;
    
    
      while(ptr!=NULL)
      {
             ptr->data=stack[i];
              i--;
             ptr=ptr->link;
      }
      }
      else
      cout<<"\n THE LIST IS EMPTY";
      }

 

Answer by batni
Submitted on 5/10/2006
Rating: Not yet rated Rate this answer: Vote
Node *Reverse (Node *p)
{
   Node *pr = NULL;
   while (p != NULL)
   {
      Node *tmp = p->next;
      p->next = pr;
      pr = p;
      p = tmp;
   }
   return pr;
}

 

Answer by Goitom
Submitted on 6/17/2006
Rating: Not yet rated Rate this answer: Vote
C# code:
public void Reverse(ref node headRef)
{
   Node first;
   Node rest;
   if (headRef == null)
      return;               // empty list base case
   first = headRef;         //eg {1,2,3}
   rest = first.Next;
   if (rest == null)
      return;               // empty rest base case
   Reverse(ref rest); // Recursively reverse the smaller {2,3} case
   //now: rest = {3,2}
   first.Next.Next = first;   // put the first elem on the end of the list
   first.Next = null;         // (tricky step -- hand trace with a drawing)
   headRef = rest;            // update the head pointer
}

 

Answer by SHASHI
Submitted on 7/3/2006
Rating: Not yet rated Rate this answer: Vote
void RecursiveReverse(NODE **head,NODE *prev,NODE *next)
{
   if(*head == NULL )
      return;

   if(next == NULL)
   {
      (*head)->next = prev;
      return;
   }

   (*head)->next = prev;
   prev = (*head);
   (*head) = next;
   
   RecursiveReverse(head,prev,(*head)->next);
}

 

Answer by Soniya
Submitted on 7/23/2006
Rating: Not yet rated Rate this answer: Vote
void reverse(struct link *list)
{
if(list!=NULL)
{
reverse(list->next);
printf("%d",list->data);
}
}



 

Answer by ahouzer
Submitted on 7/29/2006
Rating: Not yet rated Rate this answer: Vote
Node *ListReverse(Node * current)
{
   Node *temp;
   if (current->next==0)
      return current;
   temp=ListReverse(current->next);
   current->next->next=current;
   current->next=0;
   return temp;
}

 

Answer by ravi
Submitted on 8/3/2006
Rating: Not yet rated Rate this answer: Vote
All had given write answers. Not only recursion, we can use this by arrays. firstly store the data in array from the list and then insert reversely into the list from array.

 

Answer by kartikay
Submitted on 8/6/2006
Rating: Not yet rated Rate this answer: Vote
Ramuguda's and some other ppl's answers (though correct) have a shortcoming:

They try to return a local variable!!! A discussion of why this could be disastrous and very difficult to debug is available on the net.

One way to correct this is to immediately assign the returned address to a local variable in the calling program. But that breaks the 'black box' analogy of a function.
Improved:

NODE *
reverse_list(NODE *node)
{
  NODE *temp;

  if(node->next)
  {
    temp = reverse4_list(node->next);
    node->next->next = node;
    node->next =  NULL;

  }
  else
    return node;

  node = temp;
  return node;
}

call as:
proot = reverse_list(proot);


 

Answer by unknown
Submitted on 8/24/2006
Rating: Not yet rated Rate this answer: Vote
how to find the middle element in a linked list  in one traversal.

 

Answer by shilpidce
Submitted on 8/26/2006
Rating: Not yet rated Rate this answer: Vote
Can we have iterative linked list reversal using only two  temporary pointers instead of three.

 

Answer by SUJATA NEGI
Submitted on 9/10/2006
Rating: Not yet rated Rate this answer: Vote
#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int a,b;
a=10;
b=5;
a=a+b;
b=a-b;
a=a-b;
printf("a=%d",&a);
printf("b=%d",&b);
getch();
}

 

Answer by mav
Submitted on 9/11/2006
Rating: Not yet rated Rate this answer: Vote
"how to reverse a sll with extra space??"

this was my midsem xam question; now what this extra space??

 

Answer by ssss
Submitted on 9/15/2006
Rating: Not yet rated Rate this answer: Vote
<script>alert("hii")</script>

 

Answer by moiriba
Submitted on 9/20/2006
Rating: Not yet rated Rate this answer: Vote
SList *reverse(SList *head)
{
   if(head == null || head->next == null) return head;

   Slist *tmp = head->next;
   if(tmp->next == null)
   {
      tmp->next = head;
      head->next = null;
      return tmp;
   }

   Slist *newHead = reverse(tmp);
   tmp->next = head;
   head->next = null;
   return newHead;
}

 

Answer by ranbo
Submitted on 9/20/2006
Rating: Not yet rated Rate this answer: Vote
Recursion is fun to program, but on something like reversing a linked list, it can get you into trouble when the list is long.  In "real life", lists can contain hundreds, thousands, and sometimes millions of elements.  spongman'sanswer is a straightforward approach that would work fine.  The recursive answers might work, but would overflow the stack on a large list, so those should be avoided.  In general, anything done with recursion can be done without, so it should be used only when the solution is much simpler and programmer time is more important than memory efficiency, or when it is known that the recursion can't go too deep.

 

Answer by g sarada
Submitted on 9/22/2006
Rating: Not yet rated Rate this answer: Vote
struct List * reverseList(struct List *start, struct List *end){
        struct List *revHead;
        if(start == NULL && end == NULL)

                revHead = NULL;
        else if(start == NULL && end != NULL){
                revHead = end;
        }
        else{
                revHead = reverseList(start->next,start);
                start->next = end;
        }
        return revHead;
}

 

Answer by pravinsharma
Submitted on 10/11/2006
Rating: Not yet rated Rate this answer: Vote
void display_list_reverse(struct string *str)
{
  if(!str) return;

  display_list_reverse(str->next);
  printf("%c",str->info);
}

 

Answer by codie
Submitted on 10/17/2006
Rating: Not yet rated Rate this answer: Vote
thanks

 

Answer by raj
Submitted on 10/18/2006
Rating: Not yet rated Rate this answer: Vote
Answer by spongman is really superb
try thet one

 

Answer by jman
Submitted on 10/21/2006
Rating: Not yet rated Rate this answer: Vote
Node* reverse(Node* head) {
  return reverse2(NULL, head);
}

Node* reverse2(Node* prev, Node* head) {
  if (head == NULL) return prev;
  Node* nextHead = head->next();
  head->next = prev;
  return reverse2(head, nextHead);
}

 

Answer by parthiban_d
Submitted on 11/2/2006
Rating: Not yet rated Rate this answer: Vote
// ReverseList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
# include <time.h>

template < typename T >
struct Node
{
  Node() : value(0), next(0)
  {
  }

  T value;
  Node *next;
};

template < typename T >
struct List
{
  List() : head(new Node < T >()), tail(new Node < T >())
  {
    head->next = tail;
    tail->next = 0;
  }

  void add(const T &value)
  {
    Node < T > *newNode = new Node < T > ();
    newNode->value = value;
    newNode->next = head->next;
    head->next = newNode;
  }

  void reverse()
  {
    Node < T > *currentNode = head, *nextNode = currentNode->next;
    while(nextNode)
    {
      Node < T > *newNextNode = nextNode->next;
      nextNode->next = currentNode;
      currentNode = nextNode;
      nextNode = newNextNode;
    }
    tail = head;
    tail->next = 0;
    head = currentNode;
  }

  void print()
  {
    for(Node < T > *first = head->next; first != tail; first = first->next)
      std::cout << first->value << ", ";
  }

  Node < T > *head, *tail;
};

int _tmain(int argc, _TCHAR* argv[])
{
  List < int > list;
  srand(time(NULL));
  for(int i = 0; i < 10; ++i) list.add(rand());
  list.print();
  list.reverse();
  list.print();
   return 0;
}


 

Answer by Niranjan Bendre
Submitted on 12/10/2006
Rating: Not yet rated Rate this answer: Vote
reverse(Node a)
{
   if (a->next == NULL)
      return;
   else
   {
      reverse(a->next);
      (a->next)->next = a;
   }
}

 

Answer by ashwin
Submitted on 1/14/2007
Rating: Not yet rated Rate this answer: Vote
struct node * rev(struct node * home)
{
   if(home->next==NULL)
   {
   q=home;
   return(home);
   }
   t=rev(home->next);
   t->next=home;
   t=t->next;

}

Initial call
rev(home)->next=NULL
q is global

 

Answer by ssl
Submitted on 1/17/2007
Rating: Not yet rated Rate this answer: Vote
node * rr (node * n)
{
    node * m = n;
    if (n!=NULL && n->next!=NULL)
    {
       m = rr(n->next);
       n->next->next = n;
       n->next = NULL;
    }
    return m;
}
ref: http://www.employees.org/~ssl/c/Q.txt

 

Answer by batmant
Submitted on 1/30/2007
Rating: Not yet rated Rate this answer: Vote
I tried a lot of the solutions previous given and took from all of them to find what I believe is the simplest solution. It's easier to understand albeit may not be the recursion by your definition.

void reverse(node *prev, *ptr)
{
  if (!ptr) { head = prev; }
  else
  {
     reverse(ptr, ptr->next);
     ptr->next = prev;
     if (!prev) { tail = ptr; }
   }
}
call: myList.reverse(0, myList->head);

Previous to this post, I rarely used recurison, I typically reversed a linked list the following way.

void reverse()
{
  node* c = head;
  node* n = c->next;
  node* p = 0;
  while (n)
  {
    c->next = p;
    p = c;
    c = n;
    n = c->next;
   }
   c->next = p;
}

call: myList.reverse();


Anyone know which is more efficient?

Also, forgive me if I made some errors, I'm typing from memory.

http://versatile.vox.com

 

Answer by Dina
Submitted on 2/12/2007
Rating: Not yet rated Rate this answer: Vote
Can someone show me how to do it without using a temporary node and without using recursion? Peter said we should use swapping but I don't really get how.

 

Answer by Rajeesh
Submitted on 3/1/2007
Rating: Not yet rated Rate this answer: Vote
Node* Reverse( Node* node )
{
        if( node->next == NULL )
                head = node;
        else
                Reverse(node->next)->next = node;
        return node;
}

int main()
{
        head = CreateLL(10);
        Node* temp = head;
        Reverse(head);
        temp->next = NULL;
        free(temp);
        return 0;
}

 

Answer by Blue King
Submitted on 3/6/2007
Rating: Not yet rated Rate this answer: Vote
A single loop solution:

reverse(head)
{
p = head;
p1 = p.next();
p2 = p1.next();
p.next = null; // first becomes last
while (p2 != null)
{
  p1.setNext(p);  // reverse the link
  p = p1;
  p1 = p2;
  p2 = p2.next();
}

return p1; // new head
}

 

Answer by divya
Submitted on 3/8/2007
Rating: Not yet rated Rate this answer: Vote
how to reverse a doubly linked list

 

Answer by skolsur
Submitted on 3/14/2007
Rating: Not yet rated Rate this answer: Vote
static void Reverse(struct node** headRef) {
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = result;
result = current;
current = next;
}
*headRef = result;
}

 

Answer by qamama
Submitted on 3/16/2007
Rating: Not yet rated Rate this answer: Vote
ffwnfw fnwifhwifhwifwi fwifwf
f wgfpwjgfowhjegeg

 

Answer by manama
Submitted on 4/11/2007
Rating: Not yet rated Rate this answer: Vote
plain answer is this : :)
enjoy my friends... I love you all
------------------------------------
typedef struct node *NODE
reverse list( NODE first)
{
NODE cur, temp;
while(first->link!=NULL)
{
  temp=first;
  first=first->link;
  temp->link=cur;
  cur=temp;
}
return first;
}

 

Answer by programmer_guy
Submitted on 4/23/2007
Rating: Not yet rated Rate this answer: Vote
Node* ReverseList( Node ** List )   
{

   Node *temp1 = *List;
   Node * temp2 = NULL;
   Node * temp3 = NULL;

   while ( temp1 )
   {
      *List = temp1; //set the head to last node      
temp2= temp1->pNext; // save the next ptr in temp2
      temp1->pNext = temp3; // change next to privous
      temp3 = temp1;
      temp1 = temp2;
   }

   return *List;
}

 

Answer by Todd
Submitted on 5/28/2007
Rating: Not yet rated Rate this answer: Vote
Peter's answer on switching values without a temporary variable is horrible practice.

a+b is not guaranteed to be fit within the range of a or b, possibly yielding overflow, and to count on the underlying representation to correct this is also horrible practice.

 

Answer by greek
Submitted on 6/2/2007
Rating: Not yet rated Rate this answer: Vote
The recursive solution is actually worse than the iterative from an optimization standpoint - you're not really reversing the list in-place since you essentially use function calls that push on the stack as temporary storage. The iterative one is best.

 

Answer by malli
Submitted on 6/26/2007
Rating: Not yet rated Rate this answer: Vote
reverse(node *p)
{
  node *q,*r;
  r = NULL;
  while(p != NULL)
  {
    q = p->next;
    p->next = r;
    r = p;
    p = q;
  }
}

OUTPUT: r contains the reversed list

 

Answer by RJK
Submitted on 7/15/2007
Rating: Not yet rated Rate this answer: Vote
There is a bug in the previous program(without recursion one), the last pointer is left dangling. The key here is that you need two pointers to keep track of prev node and next node.
The correct code should be:
node* reverse(node* head)
{
  node* next;
  node* prev=NULL;
  node* curr=head;

  if(!head) return head;
  while(curr->next != NULL)
  {
    next=curr->next;
    curr->next=prev;
    prev=curr;
    curr=next;
  }  
  // This is required else the last node pointer is left dangling.
  curr->next=prev;
  
  return curr;

}
  





 

Your answer will be published for anyone to see and rate.  Your answer will not be displayed immediately.  If you'd like to get expert points and benefit from positive ratings, please create a new account or login into an existing account below.


Your name or nickname:
If you'd like to create a new account or access your existing account, put in your password here:
Your answer:

FAQS.ORG reserves the right to edit your answer as to improve its clarity.  By submitting your answer you authorize FAQS.ORG to publish your answer on the WWW without any restrictions. You agree to hold harmless and indemnify FAQS.ORG against any claims, costs, or damages resulting from publishing your answer.

 

FAQS.ORG makes no guarantees as to the accuracy of the posts. Each post is the personal opinion of the poster. These posts are not intended to substitute for medical, tax, legal, investment, accounting, or other professional advice. FAQS.ORG does not endorse any opinion or any product or service mentioned mentioned in these posts.

 

<< Back to: comp.lang.c FAQ list Table of Contents

[ Home  |  FAQ-Related Q&As  |  General Q&As  |  Answered Questions ]
© 2008 FAQS.ORG. All rights reserved.