Search the Q&A Archives

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

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

 Answer by Sudhakar Submitted on 1/2/2004 Rating: Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great Recursive method of reversing the linked list is the best bet !

 Answer by raghu Submitted on 3/2/2004 Rating: Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great can we reverse a singly linked list using just one variable ?

 Answer by Peter Submitted on 3/21/2004 Rating: Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great Recursion is noones friend

 Answer by mozzis Submitted on 4/30/2004 Rating: Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great Am, what else is recursion for?

 Answer by sdfsd Submitted on 6/23/2004 Rating: Rate this answer: N/A Worst Weak OK Good Great sdfsdfsdf

 Answer by basha nit Warangal Submitted on 8/20/2004 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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 gaur Submitted on 10/5/2004 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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 IceBryce Submitted on 2/24/2005 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great // // 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great ramuguda, ur solution almost always returns NULL (except that the list contains only 1 element), which is incorrect.

 Answer by RakeshPawar Submitted on 7/20/2005 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great how dos o.s can be installed

 Answer by trilogy Submitted on 8/22/2005 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great poon kha lae :)

 Answer by whats wrong with Submitted on 11/25/2005 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great who cares

 Answer by xspark86 Submitted on 2/15/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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<info;     }    return; } CALL AS:reversedisp(head)

 Answer by asdasd Submitted on 4/4/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great

 Answer by Aditi Submitted on 4/5/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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 Soniya Submitted on 7/23/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great #include #include 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: N/A Worst Weak OK Good Great "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: N/A Worst Weak OK Good Great

 Answer by ranbo Submitted on 9/20/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great thanks

 Answer by raj Submitted on 10/18/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great Answer by spongman is really superb try thet one

 Answer by Niranjan Bendre Submitted on 12/10/2006 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great how to reverse a doubly linked list

 Answer by skolsur Submitted on 3/14/2007 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great ffwnfw fnwifhwifhwifwi fwifwf f wgfpwjgfowhjegeg

 Answer by manama Submitted on 4/11/2007 Rating: Not yet rated Rate this answer: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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: N/A Worst Weak OK Good Great 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.

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.