How do you find the middle node of singly linked list of unspecified length, by traversing the list only once?
Solution:
Solution:
- Take two pointers p1 and p2.
- Let p1 and p2 point to head
- p1=p2 = head;
- Advance p1 by one node at a time and p2 by 2 nodes at a time
- p1 = p1->next;
- p2 = p2 ->next->next;
- When p2 reaches NULL, p1 will be in the middle node.
NODEPTR find_mid_node(NODEPTR head)
{
NODEPTR t1 ,t2;
t1 = t2 = head;
while(t2!=NULL && t2->next!=NULL)
{
t1 = t1->next;
t2 = t2->next->next;
}
return t1;//this is the midnode
}
How do you reverse a singly linked list?
I have written a recursive solution for reversing a list in this post . Let us discuss non-recursive solution now.
- Take two pointers p1 and p2 pointing to first and second nodes
- p1 = head;
- p2 = p1->next;
- p1->next=NULL;
- Now reverse their links
- p2->next = p1;
- But now the problem is, we have lost track of the third and subsequent nodes. So before reversing the links store third node in p3
- p1 = head;
- p2 = p1->next;
- p3 = p2->next;
- p2->next = p1;
- Now continue the process of reversing the links for next set of three nodes
- p1 = p2;
- p2 = p3;
- p3 = p3->next;
- Repeat this process until p3 reaches NULL. At this point of time, p2 will be the last node
- head = p2;
And here is the code for reversing a singly linked list.
NODEPTR reverse_list_nr(NODEPTR head)
{
NODEPTR p1,p2,p3;
p1 = head;
p2 = p1->next;
p3 = p2->next;
p1->next = NULL;
while(p3!=NULL)
{
p2->next = p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;
return p2;
}
Comments
Post a Comment