gaurav kaushik

• Oct 5th, 2006

 

1 #include 2 int main() 3 { 4 void rev(char *); 5 char src[] = "gaurav"; 6 printf("src = %s ",src); 7 rev(src); 8 printf("nnafter revrse src = %s ",src); 9 } 10 void rev(char *s) 11 { 12 char *t; 13 t = (char *)malloc(strlen(s)+1); 14 strcpy(t , s); 15 while(*t != '') 16 { t++;} 1 t--; 18 while(*s != '') 19 {*s++ = *t--;} 20 t++; 21 free(t); 22 }

Rakesh

• Oct 7th, 2006

 

n1->n2-n3->n4->n5

The problem with the single linked list is you cannot traverse back.
one easy solution is to declare an array of struc whose number of elements is equal to the number of elements in the linked list.
copy each element in the linked list to the array.
Then copy the content of the array to the linked list in the reverse order.

it works.
if u want an ex mail me: rakesh_fair_06@yahoo.com i will send a program for u

rakrak_2

 Profile Answers by rakrak_2 

• Oct 11th, 2006

 

its easy to reverse a single linked list.

just take a node from the begining and insert it in the top of the new linked list.

ex:  n1->n2->n3->n4

then take n1 and insert it in the top of new list

old=n2->n3->n4->null

new=n1->null  (give this node next value as null)

then take n2 and insert it in the top of new list

old=n3->n4->null

new =n2->n1->null

continue this method.......

here is the pseudocode
node *reverse(oldnode)
{
tempnode;
newnode=null;
while(oldnode!=null)
{
tempnode=oldnode->next;
oldnode->next=newnode
newnode=oldnode;
oldnode=tempnode
}
return newnode;
}

vipin gupta

• Oct 16th, 2006

 

To reverse a link list of any size & without using another list, u will need only 3 pointers.... First Initialize them to the startnode of the list... see the sample code below.fstPtr=startNode;secPtr = fstPtr;trdPtr=fstPtr;while(fstPtr != NULL){trdPtr = secPtr;secPtr = fstPtr;fstPtr = fstPtr->next;if(secPtr==trdPtr) secPtr->next = NULL; // for first element of the list, which will be the last elment after reversing; else secPtr->next = trdPtr;}I hope I am clearcheersVipin

vipin gupta

 Profile Answers by vipin gupta Questions by vipin gupta

• Oct 16th, 2006

 

Hello,
There is another way... If u want to reverse a link list of any size without using one more list of similar size, u will need just 3 pointers.....
see the code below:
fstPtr=startNode;
secPtr=fstPtr;
trdPtr = secPtr;
while(fstPtr != NULL)
{
trdPtr = secPtr;
secPtr=fstPtr;
if(secPtr == trdPtr)
secPtr->next = NULL; // for the first element; that will become the last node of reverse list
else
secPtr->next = trdPtr;
fstPtr = fstPtr->next;
}
I hope I am clear.
thanx
Vipin

NHKR

• Oct 19th, 2006

 

Here is one more way,

ex n1->n2->n3->n4->null

Read from the start and keep pushin on to a stack until null.

Now, the stack will be n4->n3->n2->n1

Now, pop from the stack and frame the list.

Easy, isnt't it!!!

Regards,

NHKR

vipin gupta

 Profile Answers by vipin gupta Questions by vipin gupta

• Oct 20th, 2006

 

Yes, it is easy. But, the memory requirements for stack will depend on the size of link list.
If u have a very large link list (say 30,000 integer elements), it would take a stack of (30,000 * 4) bytes of space to reverse the list. Whereas, the method proposed by me in previous reply, would take only 3 pointers (3 *4 = 12 bytes) to reverse a list of any size.......

U will have a tradoff between simplicity & efficiency, choice is yours.....

NHKR

• Oct 20th, 2006

 

One more version:

 

#include<stdio.h>
#include <malloc.h>

struct a1 {

    int a;
    struct a1 *next;
   };

 

int add(struct a1*);

display(struct a1*);

struct a1* rev(struct a1*);

main()

{

 struct a1 *head;

 head=(struct a1*)malloc(sizeof(a1));
 printf("Enter the value for the head noden");
 scanf("%d",&head->a);
 head->next=NULL;
 while(add(head));
 display(head);
 head=rev(head);
 display(head);
 

}

int add(struct a1 *head)

{

struct a1 *start;

start=head;

while(start->next!=NULL)
{

 start=start->next;
}

int addmore=0;
 struct a1 *news;

 news=(struct a1 *)malloc(sizeof(a1));
 printf("Please enter the value for next noden");
 scanf("%d",&news->a);
 start->next=news;
 news->next=NULL;
 printf("Press 1 for add more and 0 for stop addingn");
 scanf("%d",&addmore);
 return addmore;
}

display(struct a1 *head)

{

 while(head->next!=NULL)
 {
  printf("%d [%x]->",head->a,head->next);
  head=head->next;
 }
 printf("%d [%x]->",head->a,head->next);

 printf("nnnn");
}

struct a1* rev(struct a1 *head)
{

 struct a1 *first,*newlast,*newhead,*second,*temp;
 
 first=head;

 while(head->next!=NULL)
 {
  head=head->next;
 }

 newlast=newhead=head;

 temp=newlast->next=first;
 first=first->next;
 temp->next=NULL;

 while(first!=newhead)
 {
 
 temp=newlast->next;
 second=newlast->next=first;
 first=first->next;
 second->next=temp;

 }

 

 return newhead;

}

vipin gupta

 Profile Answers by vipin gupta Questions by vipin gupta

• Oct 20th, 2006

 

well, I would say this version is good as it gives better readability.... But, it makes use of 6 pointers (whereas 3 pointer would be enough: See the previous reply posted by me). Still, It is OK , as only 24 bytes of memory is needed to reverse a list of any size..... good work

NHKR

• Oct 25th, 2006

 

Yea,I was focussed on helping an interview attending person with the details so that he can understand what is the core logic, so that he can understand it easily.I didnt focus on programming skills as of now.Regards,NHKR

Trevor

• Oct 27th, 2006

 

There is only ONE GOOD answer to this question.This is a standard interview question I ask and I dismiss any stack / array type solutions.This should be done in O(n) time and using O(1) space.Use 3 pointers (prev, current, next) and just walk down your list pointing it in the opposite direction incrementing your pointers accordingly.

narsimha rao T

• Nov 6th, 2006

 

By taking 3 pointers we can reverse a linked list here is the function that reverses a linked list

reverse()

{

struct node *p,*q,*r;

*p=first;//p points to first node of the list

*q=NULL;

while(*p!=NULL)

{

r=p->next;//r pointing to next node to p

p->next=q;

q=p;

p=r;

}

first=q;

}

This will definitely work Try this and if you have any queries mail me back

manik sheeri

• Nov 7th, 2006

 

take 2 pointers of the type of node of the linked list. pseudo code is given below: head=start pointer to the list<next){ ptr2=ptr2->next;ptr2->next=ptr1;ptr1=ptr2;}head->next=NULL; /*making sure that the list ends with NULL*/head=ptr2;>>

manik sheeri

• Nov 8th, 2006

 

sorry guyzzz.....by mistake i wrote the solution for other question .well, this problem can be solved by using three pointers ( of linked list node type)p1=points to start of the listp2=p1->next;while(p2){ p3=p2->next; p2->next=p1; p1=p2; p2=p3;}

Sudhir Kumar S

• Nov 14th, 2006

 

#include#includetypedef struct node NODE;struct node{ int val; NODE *next;};void insertNode(void *head,int val){ NODE *temp; if(*(NODE **)head) temp = *(NODE**)head; if(*(NODE **)head){ while(temp->next!=NULL){ temp = temp->next; } temp->next = (NODE*)malloc(sizeof(NODE)); temp = temp->next; temp->val = val; temp->next = NULL;//Not needed for *nu(i)x OS's ! } if(!*(NODE **)(head)){ *(NODE **)head = (struct node*)malloc(sizeof(NODE)); (*(NODE **)(head))->val = val; (*(NODE **)(head))->next = NULL;//Not needed for linux/unix OS's ! }} void printNode(NODE *ptr){ NODE *temp = ptr; printf("nn"); while(temp->next!=NULL){ printf("%d-->",temp->val); temp = temp->next; } printf("%d",temp->val);}void freeNode(NODE **head){ if(*head){ free(*head); }}void reverseNode(NODE **head){ NODE *curr,*prev,*next; prev = (*head); curr = (*(head))->next; next = curr->next; while(curr->next!=NULL){ curr->next = prev; prev = curr; curr = next; if(curr->next==NULL){ curr->next = prev; break; } else next = curr->next; } (*(head))->next = NULL; *head = curr;}int main(){ long int i; NODE *head = NULL; for(i=1;i<=10;i++) insertNode(&head,i); printNode(head); printf("nn"); reverseNode(&head); printNode(head); printf("nn"); freeNode(&head); return 0;}

vishwa

• Nov 16th, 2006

 

reversing a sll is easy by using recursion we have to call a function again and again once it reach last node and once it reaches last node create a new LL and copy in it deleting the old node.

 

Sundar A

• Nov 29th, 2006

 

A simple recursive function should do the trickAssuming "node" being typedef-ed to your link structure and "head" being global pointer pointing to your first elementnode *reverse(node *n){ node *prev; static node *tmp_head; if (n->next == NULL){ tmp_head = n; return n; } prev = reverse(n->next); prev->next = n; if (head == n){ head = tmp_head; n->next = NULL; } return n;}/** NOTE: I'ven't tested this code!! HOPE THIS WILL WORK **/