CareerCup

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.


if linked list is not sorted then you can you two pointer fast and slow to check the loop

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;
}

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.

void findLoop(Node head) {

                Node temp = head;
                while (null != temp.next) {
                        if (temp.data < temp.next.data) {
                                System.out.println("Loop is available " + temp.data);
                                return;
                        }
                }

                System.out.println("Loop is not available ");
        }