You are given a pointer to the head of singly linked list. Usually, each node in the list only has a pointer to the next element, and the last node’s pointer is NULL. Unfortunately, your list might have been corrupted, so that the last node has a pointer back to some other node in the list.
Design a linear-time algorithm (using only a constant extra space) to determine whether the linked list is corrupted. Your algorithm must not modify the list.
Find the node in linear time, where last node is pointing.
Posted: Jun 12 '12
Seen: 166 times
Last updated: Oct 19 '12