9. Find whether a list is even or odd.
10. Reverse a link list with/without recursion.
11. Shuffle two link list of same size.
12. Merge two sorted link list.
13. Find whether two list are intersecting or not.
14. Detect a loop in link list.
15. Remove loop from link list.
16. Find the length of loop.
17. Find the kth element from end.
10. Reverse a link list with/without recursion.
11. Shuffle two link list of same size.
12. Merge two sorted link list.
13. Find whether two list are intersecting or not.
14. Detect a loop in link list.
15. Remove loop from link list.
16. Find the length of loop.
17. Find the kth element from end.
9. Find whether a list is even or odd.
ReplyDeletea) Keep counting.
b) Use a bool for flag
c) Without any variable
int isOdd ( struct node *head )
{
Head = head->next;
While ( head)
{
If ( head->next == NULL )
Return 1;
Head = head->next->next;
}
}
10. Reverse a link list with/without recursion.
Void reverselist( struct node *head )
{
Struct node *prev, *current, *temp;
Prev = NULL;
Current = head->next;
While ( current )
{
Temp = current->next;
Current->next = prev;
Prev = current;
Current = temp;
}
Head->next = prev;
}
11. Shuffle two link list of same size. If p and q are head pointers.
Struct node *newhead = p;
While (q )
{
Swap(&p->next, &q);
P = p->next;
}
12. Merge two sorted link list.
13. Find whether two list are intersecting or not.
a) Use negation technique. Traverse list 1 and negate elements. Traverse list 2 and return first negated element.
b) Hashtable: insert node in hashtable. If found collision return element.
c) Length of list 1 = m length of list 2 = n. Traverse |m-n| element and then start comparing.
14. Detect a loop in link list.
a) Maintain a flag for each node visited. If you see any node already visited then a loop.
b) use hashtable for nodes.
c) Take two pointers. Increment first by one and another by two.
Note: Application kernel programming and random number generator.
15. Remove loop from link list.
Use the loop detection approach and as soon as you know node->next is repeated, make it null.
16. Find the length of loop.
Use any of the above three approach and keep a counter until a node repeated.
17. Find the kth element from end.
a) Bruteforce: count the list nodes once and go for the (n-k) node next time.
b) Maintain two pointer, both pointing to I and i-k node. So when pointer 1 point at n second one will point to n-k.