CTCI Challange, DAY 4

Day 4:-

Problem statement:- Linked Lists: Detect a Cycle

I have studied a lot on linked lists but was very lazy in implementing its functionalities as i felt its very easy while watching it in videos.But when I started working on this It was very confusing :-)

Solved it in 30 min,very happy and was able to run it in first iteration only,Double happy :-)

On Paper:

Program:-

public class LinkedList {
    /*
Detect a cycle in a linked list. Note that the head pointer may be 'null' if the list is empty.
A Node is defined as:
*/
    class Node {
        int data;
        Node next;
    }

    static Node head;

    boolean hasCycle(Node head) {
        if (head == null) {
            return false;
        }
        String result = "no cycle";
        Node temp = head;
        Map<Node, Integer> map = new HashMap<>();
        while (temp.next != null) {
            if (!map.containsKey(temp.next)) {
                map.put(temp, 1);
                temp = temp.next;
            } else {
                result = "cycle exist";
                break;
            }
        }
        System.out.println(result);
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        LinkedList ll = new LinkedList();
        for (int i = 0; i < n; i++) {
            ll.insert(scan.nextInt());
        }
        ll.hasCycle(head);
    }

    private void insert(int data) {
        if (head == null) {
            head = new Node();
            head.data = data;
            head.next = null;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        Node n = new Node();
        n.data = data;
        n.next = null;
        temp.next = n;
     /*   if (data == 2){
            temp.next = head.next;
        }*/
    }
}