Expedia Interview Question
Software Engineer in TestsCountry: India
Interview Type: Phone Interview
this will find whether there is loop or not in sorted linked list
boolean isLooped(node *head) {
if (head == nul) {
return false;
}
if (head->next == null) {
return false;
}
node *temp = head;
while (temp->next!=null) {
if (temp->value < temp->next->value) {
return true;
}
temp = temp->next;
}
return false;
}
nice. This works only if the input has no duplicates. For example, if the input is
1->3->3->3->(back to the 2nd node)
Thanks X for finding that out...
in that case we have a pointer to the first node from where element are going to duplicate. if temp == firstDupNode, then list is having loop.
if let say more than one elements are duplicate then we have to maintain the firstDupNode to the node which has the duplicate value as temp node.
put two pointers pointing to head. first pointer move 2 each time, the second pointer just 1. if they meet. then there is a loop.
pointer1 = head.next.next.
pointer2 = head.next.
while(pointer1 != null){
pointer1 = pointer1.next
pointer2 = pointer2.next
if pointer1 == pointer2 return has loop
pointer1 = pointer1.next
if pointer1 == pointer2 return has loop
}
public static void FixFaultyNodesInSortedLinkedList()
{
//Prepare the mock list
var head = new SingleLinkedList<int>() { Value = 1 };
var cur = head;
for (int i = 0; i < 5; i++)
{
cur.Next = new SingleLinkedList<int> { Value = i + 2 };
cur = cur.Next;
}
cur.Next = head;
//***************************************************
if (head == null || head.Next == null)
return; //return head;
cur = head;
while (cur.Next != null)
{
if (cur.Value > cur.Next.Value)
cur.Next = null; //fix by setting the next value null. ignore the rest of list for now.
else
cur = cur.Next;
}
Console.WriteLine("Print head to tail.");
}
Assuming the type of data stored in linked list is int value, above solution fits the bill.
I linked list is sorted then, just iterate through the list and check if you get any node with lower value then the previous node, if yes then linked list has a loop.
- sjain May 21, 2013if linked list is not sorted then you can you two pointer fast and slow to check the loop