How will you find the middle node in a linked list?
Sol : Take two pointers.Move one pointer at x speed and second pointer at 2x speed.When second pointer reaches the end of the linked list,first pointer reaches middle of the linked list.
1st with head->next
2nd with head->next->next
How will you find the node with position 3/4 of the total number of nodes ?
fast pointer : slow pointer = 4:3
slow = ptr->next->next->next
fast = ptr->next->next->next->next
For M/N th node,move first pointer at Mx speed and second pointer at Nx speed.When fast pointer reached the end of the list,slow pointer will be at required position.But this works best for even number of nodes in list.
Sol : Take two pointers.Move one pointer at x speed and second pointer at 2x speed.When second pointer reaches the end of the linked list,first pointer reaches middle of the linked list.
1st with head->next
2nd with head->next->next
How will you find the node with position 3/4 of the total number of nodes ?
fast pointer : slow pointer = 4:3
slow = ptr->next->next->next
fast = ptr->next->next->next->next
ptr1 should move 4 nodes at a time
ptr2 should move 3 nodes at a time,
When the ptr1 reaches the end the ptr2 will be pointing to 3/4t.
For M/N th node,move first pointer at Mx speed and second pointer at Nx speed.When fast pointer reached the end of the list,slow pointer will be at required position.But this works best for even number of nodes in list.
For odd numbers we need to compromise like finding the middle node.
No comments:
Post a Comment