To find loop in a singly linked list without using slow and fast pointer

Question

As we know that for detecting loop in a linked list, we use slow pointer and fast pointer in which firstly we initialize two node slow and fast with head node
then we traverse fast pointer two step ahead and slow with one step ahead.
If we find both addresses are equal, then, there is loop otherwise if fast==null || fast.next==null then there is no loop.

Now my question is
"Is there any possibility to detect loop in singly linked list without using fast and slow pointer ?"

Any idea will be appreciated.
Thanks in advance.

Jim Mischel · Accepted Answer · 2016-10-30 13:04:16Z

There are at least two other solutions.

An O(n^2) solution is to keep track of the node numbers. At each node, go back to the head and count how many next operations it takes to reach the current node. If you get to the nth node before you do n next operations, then there's a loop in your list. That is:

// assuming head is not null, and head doesn't point to itself
nodeNumber = 1
current = head.next
while (current != null)
{
    p = head
    counter = 0
    while (p != current && counter < nodeNumber)
    {
        p = p.next
        counter = counter + 1
    }
    if (p != current)
        there's a loop
    nodeNumber = nodeNumber + 1
}

A destructive method is to reverse the links as you go. If there's a loop in the linked list, then when your pointer is equal to null it will be at the root. That is:

if (head == null) || (head.next == null)
    no loop

prev = head
current = head.next
while (current != null)
{
    // save next position
    next = current.next
    // reverse the link
    current.next = prev
    // and move to the next node
    prev = current
    current = next
}
if (prev == head)
    there is a loop

That does have the disadvantage of destroying the list if there's a loop in it. If there's not a loop, you can go back through the list and reverse the links.

Bhagwati Malav · Accepted Answer · 2016-11-01 18:36:58Z

1

Yes, of course. Most intuitive way is to traverse each node and check if you have visited this node. If you would have visited this node earlier, this means that there is a cycle and this particular node is the start of cycle.

To check if you have visited this node earlier you can maintain a hash-set which allows you to check for presence of an element in O(1) time complexity. Check the below pseudo code.

Time Complexity - O(n)

Space Complexity - O(n)

boolean isCyclic(Node head){
  HashSet<Node> set = new HashSet<Node>();    
  while(head != NULL){
    if(set.contains(head))
       return true;
    set.add(head)
    head = head.next  
  }
  return false;
}

edited Nov 1, 2016 at 18:36

Bhagwati Malav

3,5592 gold badges22 silver badges35 bronze badges

answered Oct 29, 2016 at 11:25

Sulabh Kumar

1018 bronze badges

1 Comment

Shree Prakash Over a year ago

first of all thanks. it's nice approach. Is it possible without using extra space O(n).?

Collectives™ on Stack Overflow

To find loop in a singly linked list without using slow and fast pointer

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related