CareerCup

save first node pointer
create an empty set
while next node is not the first node
check if the node value is already present in the set
if present, current value is a duplicate
else add node value to a set and go to next node

O(n)

boolean containsDups(Node slist){
  
       Node curr = slist;
       HashSet<Integer> set = new HashSet<Integer>();
       do{
          
            if(set.contains(curr.value))
                return true;
            else { 
                 set.add(curr.value);
              } 
           curr = curr.next;
         } while(curr != slist);

      return false;
 }

Use a slow and fast pointer to detect the loop. When loop is detected replace the fast pointer with the start and increment both until they meet, i.e., the start of the loop. Check for duplicates in using the value of slow pointer. Running time O(n)

package datastructure;

import java.util.HashMap;

public class CircularDuplicate {
	public static boolean isDuplicate(SNode s) throws Exception{
		HashMap<Integer, Boolean> table= new HashMap<Integer, Boolean>();
		SNode fast=s;
		SNode slow=s;
		if(fast.next==null)
			throw new Exception("not circular");
		fast=fast.next.next;
		table.put(slow.v, true);
		slow=slow.next;
		while(fast!=slow){
			if(fast==null || fast.next==null)
				throw new Exception("not circular");
			fast=fast.next.next;
			if(table.get(slow.v)!=null)
				return true;
			else
				table.put(slow.v, true);
			slow=slow.next;
		}
		fast=s;
		while(fast!=slow){
			if(table.get(slow.v)!=null)
				return true;
			else
				table.put(slow.v, true);
			slow=slow.next;
			fast=fast.next;
		}
		return false;
	}
	public static void main(String[] args) throws Exception{
		SNode s= new SNode(1);
		s.next=new SNode(2);
		s.next.next=new SNode(3);
		s.next.next.next=new SNode(4);
		s.next.next.next.next=new SNode(5);
		s.next.next.next.next.next=new SNode(1);
		s.next.next.next.next.next.next=new SNode(7);
		s.next.next.next.next.next.next.next=s.next.next;
		System.out.print(isDuplicate(s));
	}
}
class SNode{
	public SNode next;
	public int v;
	public SNode(int v){
		this.v=v;
	}
}

We can calculate the length of the circular list in O(n) time. Then do a O(n^2) comparision to check for duplicates. Here's my code for it :

bool hasDuplicates(node* slist){
node* start = slist;
node* n = slist;
node* m;
int len = 0;

//Calculate the length
if(n != NULL)
count++;

//Calculate the length

while(n->next != start){
count++;
n = n->next;
}


n = slist;
m = slist;

// check if some dupliacte is present
for( int i = 0 ; i < count ; i++){
m = n;
for( int j = i + 1; j < count ; j++){
m = m->next;
if( m->val == n->val)
return true;
}
n = n->next;
}

//Duplicate not found
return false;
}

traverse the link list and keep the value in a hash table
while inserting the value in hash if it is found that the value is already in the list then it is the duplicate

traverse the link list and keep the value in a hash table
while inserting the value in hash if it is found that the value is already in the list then it is the duplicate

add linked list items into dictionary and then traverse and find duplicates. Here is c# code

class Program
{
static void Main(string[] args)
{
CircularList cl = new CircularList();
cl.insertToStart(0);
cl.insertToStart(1);
cl.insertToStart(2);
cl.insertToStart(3);
cl.insertToStart(4);
cl.insertToStart(4);
cl.insertToStart(4);
cl.insertToStart(5);
cl.traverse();
Console.WriteLine(cl.isDuplicate().ToString());
}
}

class CircularList
{
Dictionary<int, bool> d = new Dictionary<int, bool>();

private listNode head;
private listNode tail;
private int size = 0;

private class listNode
{
public int item;
public listNode next;
}

private listNode find(int index)
{
listNode cur = new listNode();
cur = head;
for (int i = 0; i < index; i++)
{
cur = cur.next;
}
return cur;
}

public void insertToStart(int item)
{
listNode newNode = new listNode();
if (head == null)
{
head = newNode;
tail = head;
head.next = tail;
head.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
else
{
newNode.item = item;
newNode.next = head;
tail.next = newNode;
head = newNode;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
++size;
}

public void insertToEnd(int item)
{
listNode newNode = new listNode();
if (head == null)
{
head = newNode;
tail = head;
head.next = tail;
head.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
else
{
tail.next = newNode;
newNode.next = head;
tail = newNode;
newNode.item = item;
if (d.ContainsKey(item))
{
d[item] = true;
}
else
{
d.Add(item, false);
}
}
++size;
}

public bool isDuplicate()
{
listNode tmp = head;
bool var = false;
while (tmp.next != head)
{
if (d[tmp.item] == true)
{
var = true;
break;
}
else
{
var = false;
}
tmp = tmp.next;
}
return var;
}

public void traverse()
{
listNode tmp = head;
while (tmp.next != head)
{
Console.WriteLine(tmp.item.ToString());
tmp = tmp.next;
}
}
}

how about !
do merge sort on list (by fixing start and end pointer)
then scan once , compare with neighbour node if equal return true
no space required.
time complexity nlog n+ 0(n) = 0 (nlog n)

any thought ?

Possible solution:
Time complexity: worst case: (n)
Space complexity: worst case: (n)

Input Data structure: Singly linked list.

class Node{
    Integer value;
    Node next;
}
boolean hasDuplicates(Node start){
        HashSet<Integer> set = new HashSet<Integer>();
        Node current = start;
        do{
            if(set.contains(current.value)){
                return true;
            }else{
                set.add(current.value);
                current = current.next;
            }
        }while(current != start);
        
        return false;
    }

/* finding duplicate using hash table */

int find_duplicate(node **head)
{
node *result=*head;
int return_val=0;
int hashtable[50]={NULL}; /* table has to be modified based on the data range */
node *slow=*head;
node *fast=*head;
fast=fast->link->link;
while (fast != slow ) /* assumed the given link list is circular */
{
fast=fast->link->link;
if(hashtable[slow->data]==0)
hashtable[slow->data]=true;
else if(hashtable[slow->data] >= 1)
{
return return_val=1; /* found duplicate */
} /* objective was just to print true incase duplicate found */
slow=slow->link;

}
if(fast==slow) /* its used to find the start of the circle */
{ /* when the slow reaches the circle, the fast would also
do a roatation so we can make sure that we check for duplicate */
slow=*head;
while (slow != fast)
{
slow=slow->link;
fast=fast->link;
if(hashtable[fast->data]==0)
hashtable[fast->data]=true;
else if(hashtable[fast->data] >= 1)
{
return return_val=1; /* found duplicate */
}

}
return 0; /* no duplicate */ /* it also means that we traversed the entire link list now */
}

}

2 hash tables. 1 keeps track of Node addresses and the other keeps track of the number of duplicates of a certain value.

O(n) time complexity and O(2n) space complexity-

HashTable A <address, boolean (visited already?)>
HashTable B <value, number that this value has occurred in our traversal>

This is my java code using arraylist. But using hashset would have a lesser time complexity.

class Nodedup{
	Nodedup next;
	int data;
	Nodedup(int x){
		data=x;
	}
}
public class CircularLLDuplicate {

	Nodedup root;
	ArrayList<Integer> l=new ArrayList<Integer>();
	boolean FindDup(Nodedup r){
		Nodedup temp=r.next, start=r;
		while(temp!=start){
			
			if(l.contains(temp.data)){
			
				return false;
			}
			l.add(temp.data);
			temp=temp.next;
		}
		
		return true;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CircularLLDuplicate link=new CircularLLDuplicate();
		
		link.root=new Nodedup(1);
		link.root.next=new Nodedup(2);
		link.root.next.next=new Nodedup(3);
		link.root.next.next.next=new Nodedup(4);
		link.root.next.next.next.next=new Nodedup(5);
		link.root.next.next.next.next=link.root;
		
		System.out.println(link.FindDup(link.root));
		
		
	}

}