JAVA EXAMPLE PROGRAMS

Program: Find length of a loop in a LinkedList.

Problem Description:

Write a simple code to identify given LinkedList has a loop and if loop is present then calculate the lenght of a loop. Length of a loop is count of nodes with in the loop. If loop is not present then it should return 0.

The loop count is 5 in the below image.

The below diagram illustrates linked list loop/cycle:

In our last example, we have used Floyd’s Cycle detection algorithm to terminate when fast and slow pointers meet at a common point. The common point is one of the loop node. Here is our approach:

We store the reference of the common point in a temporary variable.
Initialize a counter with 1.
Start iterating to next node from the common point and increment the counter till we again reach the common point.
At that point, the counter value will be equal to the length of the loop.

LinkedListLoopCount

package com.java2novice.algos;

import java.util.HashSet;
import java.util.Set;

public class LinkedListLoopCount {

    static class Node {
        int data;
        Node next;
        Node(int tmp) {data = tmp;}
    }

    public static void main(String[] a){

        Node n1 = new Node(34);
        Node n2 = new Node(25);
        Node n3 = new Node(31);
        Node n4 = new Node(56);
        Node n5 = new Node(45);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n3;

        System.out.println("Loop count: "+identifyLoopCount(n1));
    }

    static int identifyLoopCount(Node head) {

        Node slowMv = head;
        Node fastMv = head;
        while (slowMv != null && fastMv != null && fastMv.next != null) {
            slowMv = slowMv.next;
            fastMv = fastMv.next.next;
            if(slowMv == fastMv) {
                return loopCount(slowMv);
            }
        }
        return 0;
    }

    static int loopCount(Node node) {

        int count = 1;
        Node tmp = node;
        while(tmp.next != node) {
            count++;
            tmp = tmp.next;
        }
        return count;
    }
}

Output:

Loop count: 3

<< Previous Program | Next Program >>

List Of All Interview Programs:

Java2Novice - YouTube Channel

Java2Novice

Knowledge Centre

Difference between Enumeration and Iterator

The functionality of Enumeration and the Iterator are same. You can get remove() from Iterator to remove an element, while while Enumeration does not have remove() method. Using Enumeration you can only traverse and fetch the objects, where as using Iterator we can also add and remove the objects. So Iterator can be useful if you want to manipulate the list and Enumeration is for read-only access.

Famous Quotations

The pessimist complains about the wind; the optimist expects it to change; the realist adjusts the sails.

-- William Arthur Ward

About Author

I'm Nataraja Gootooru, programmer by profession and passionate about technologies. All examples given here are as simple as possible to help beginners. The source code is compiled and tested in my dev environment.

If you come across any mistakes or bugs, please email me to [email protected].

Most Visited Pages

Other Interesting Sites

Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle.