Answer:
Here, start node(set to Head of the list), and the last node(set to NULL initially) are given.
The middle is calculated using two pointers approach.
Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.
If middle’s data matches the required value of search, return it.
Else if middle’s data < value, move to upper half(setting start to middle's next).
Else go to lower half(setting last to middle).
The condition to come out is, either element found or entire list is traversed. When entire list is traversed, last points to start i.e. last -> next == start.
See attached pictures.
Explanation:
See attached pictures for detailed explanation.
