Welcome, %1$s. Please login or register.

February 18, 2018, 10:51:27 AM
: 1
: Reverse a singly linked list  ( 3477 )
« : May 12, 2007, 12:20:19 AM From Shrinidhi»



Reverse a singly linked list


Reverse a given singly linked list.

 
Liked It? Share it!

              


« #1 : May 12, 2007, 12:21:24 AM From Shrinidhi»



Solution:
1.   Keep 2 pointers. Say A and B.
2.   Make A point to head and B point to the next of head.
3.   Make A->next = NULL
4.   Make B->next = A.
5.   Move B and A by one node.
6.   Repeat step 4 and 5 until B reach NULL. Make A the head.
7.   The list is reversed.


« #2 : May 24, 2007, 01:13:53 PM From satyadb4u»

once you make A point to NULL. How can you make it to move by one node.?i hope i am clear. Can ypu please put the code if possible.
« #3 : May 24, 2007, 10:22:24 PM From Prateek»

Nice observation. He has missed out on how to proceed by a node. Its not possible without an additional pointer.

Solution:
1.   Take 3 pointers. Say A and B & C
2.   Make A point to head and B point to the next of head. C point to next of B.
3.   Make A->next = NULL
4.   Make B->next = A. A=B. B=C. C=B->next. This will move pointer A, B & C by one node.
5.   Repeat step 4 until C=NULL. Then Make B->next=A and make B head.
6.   The list is now reversed.


node *reverse_list(node *list)
{
    node *A, *B, *C;

    if(!list || !list->next)
        return list;
    A=list;
    B=list->next;
    C=B-next;
    A->next = NULL;

   while( C != NULL )
   {
                             // A --> B --> C
        B->next = A;         // A <-- B --> C
        A=B;                 //       B(A)--> C
        B=C;                 //        A  --> B(C)
        C=B->next;           //        A  --> B  --> C
   }
   B->next = A;
   return B;                 //return head
}
« #4 : May 25, 2007, 11:26:42 AM From satyadb4u»

Thi is a good one...But i think u missed a statement...

initially setting a->next to NULL

what ur opine...
« #5 : May 28, 2007, 01:46:05 PM From nitt.vishal»

node *reverse ( node *ptr)
{

         if(ptr->next !=null)
{
         reverse(ptr->next)
         ptr->next->next = ptr
ptr->next = null
}
else
   head = ptr;

}
 
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer