Reversing Singly Linked List

Question

To reverse a Singly Linked List is the below is correct code? (or) need to change 

Struct node *reverse(struct node *start)
{
Struct node *prev,*ptr,*next;
prev=NULL;
ptr=start;
while(ptr!=NULL)
{
next=ptr->link;
ptr->link=prev;
prev=ptr;
ptr=next;
}
start=prev;
return start;

 

 

Plz tell me, is here all link updating correctly?

Comments

yes it is

---

Can u explain?

---

code is correct, there is no error.

---

how? give some small explaination

---

here 3 pointer. prev, ptr, next

Say there are 3 node in LL.

1---->2----->3

Now, next pointing to 2nd node

Then, ptr->link eliminated, as it is going to be NULL

Now any easy way to see, if it is reversing?

---

initially, 1 ---> 2 ---> 3

pre = next = NULL, ptr points to the element 1.

 

ptr != Null ===> enter into loop

   1) making next as element 2

   2) making element 1 --> link  = prev = NULL

   3) making prev as element 1

   4) making ptr as element 2

 

ptr != Null ===> enter into loop

   1) making next as element 3

   2) making element 2 --> link  = prev = element 1

   3) making prev as element 2

   4) making ptr as element 3

 

ptr != Null ===> enter into loop

   1) making next as NULL due to 3 --> next = NULL

   2) making element 3 --> link  = prev = element 2

   3) making prev as element 3

   4) making ptr as NULL

 

ptr != NULL ===> out of loop.

start = prev ===> making 3 as start of the linked list.

3 ---> 2 ---> 1

---

thanks

No, other short procedure, na?

We need to execute every line of code?

I am asking because,in exam  there are so many similar type option to be checked :(

---

Yes, there is no shortcut mam

We have to check each and every line

---

@Shaik Masthan

here start is pointing to last node, that is true

But is it creating reverse links too?

I mean B-->A

and C-->B?

---

yes.... due to ptr -> link = prev

---

@Shaik

will reversing linked list take O(n) time?

will find kth node from the end of a linked list take O(n)  time?

---

@Shaik Masthan

---

yes mam !

But note that there are more approaches for this query !

Answer 1

reverse(p=q=null)

{

while(s!=0)

{p=q;

q=s;

s=s->next;

q->next=p;

}

s=q;

return(s);

}

 

try this program to reverse tha single link list.

 

where p and q having extra 2 poniter.