We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Linked Lists
  4. Cycle Detection
  5. Discussions

Cycle Detection

Sort 1236 Discussions, By:

  • sonivishal_offi1
     + 0 comments

    Java Solution 

     static boolean hasCycle(SinglyLinkedListNode head) {
        SinglyLinkedListNode fp = head;
        SinglyLinkedListNode sp = head;
        
        while(fp != null && fp.next != null){
            fp = fp.next.next;
            sp = sp.next;
            
            if(sp == fp){
                return true;
            }
        }
        return false;
    }

  • kartikeysri19
     + 0 comments

    Python Solution

    def has_cycle(head): nodes=set() if head==None: return 0 while head!=None and head.next: if head in nodes: return 1 else: nodes.add(head) if head.next.next!=None: head=head.next else: if head.next in nodes: return 1 else: return 0 return 0

  • macdonald_l_kyn
     + 0 comments

    Python Solution

    def has_cycle(head):
    f = head.next
    s = head
    while f and s and f.next:
        if f == s:
            return 1
        f = f.next.next
        s = s.next
    return 0

  • gimmins
     + 0 comments

    since I wasn't able to get the JavaScript to work, and sounds like others have experienced it as well, here's a code you can run in dev console or jsfiddle to see how linked list with cycle and non-cycle can be worked out

    class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  
  add(value) {
    let newNode = new Node(value);
    
    let iter = this.head;
    
    if (iter === null) {
      this.head = newNode;
    } else {
      while (iter.next !== null) {
        iter = iter.next;
      }
      
      iter.next = newNode;
    }
  }
}

let nonCycledLinkedList = new LinkedList();
let cycledLinkedList = new LinkedList();

function createNonCycledLinkedList() {
	nonCycledLinkedList.add(1);
  nonCycledLinkedList.add(2);
  nonCycledLinkedList.add(3);
  nonCycledLinkedList.add(4);
  nonCycledLinkedList.add(5);
  nonCycledLinkedList.add(6);
}

function createCycledLinkedList() {
  cycledLinkedList.add(1);
  cycledLinkedList.add(2);
  cycledLinkedList.add(3);
  cycledLinkedList.add(4);
  cycledLinkedList.add(5);
  cycledLinkedList.add(6);
  
  let tail = cycledLinkedList.head;
  let cycle = cycledLinkedList.head;

  while (tail.next !== null) {
    tail = tail.next;
  }
  
  const cyclePos = 3;
  
  for (let i=0; i<cyclePos; i++) {
    cycle = cycle.next;
  }
  
  tail.next = cycle;
}

createNonCycledLinkedList();
createCycledLinkedList();

function isCycle(list) {
  let rabbit = list.head;
  let turtle = list.head;
  
  rabbit = rabbit.next.next;
  
  while (turtle && rabbit && rabbit.value !== turtle.value) {
    rabbit = rabbit.next.next;
    turtle = turtle.next;
  }
   
  if (!rabbit || !turtle) {
    return console.log("the linked list is not cycle")
  }
  
  if (rabbit.value === turtle.value) {
    return console.log("the linked list is cycle");
  }
}

isCycle(nonCycledLinkedList);
isCycle(cycledLinkedList);

  • antoniocostabr
     + 0 comments

    Python 3:

    def has_cycle(head):
    nodes = set()
    
    if head ==None:
        return 0
    while head !=None:
        if head in nodes:
            return 1
        else:
            nodes.add(head)
            head = getattr(head,'next')
    return 0
Load more conversations