CareerCup

Input Output explanation
1. 1->2->2->3->4 1->2->3->4 the sanity path
2. 1->1->2->3 1->2->3 border case duplicate at head
3. 1->2->3->3 1->2->3 border case duplicate at tail
4. 1->1->1->1 1-> all duplicates
5. 1->2->3->4 1->2->3->4 no duplicates
6. 1->2->3->2 1->2->3 duplicates in alternative positions (not consecutive)
7. Int.Min-1->2->1->Int.Max+1 2->1 test to make sure that the linked list structure handles numbers out of int range (the question didn't specify the range)
8. 1->2->1->2->3->3 1->2->3 each node has a duplicate
9. -1->0->1 throw exception should verify that erroroneous data is not being handled
10. 2->3->3->2->1 verify that the head is 2 making that the spec is being met
11. 1->1->1->1->1->1->1->2 1->2 just one non duplicate
12. test for a huge linked list that would potentially overflow memory and verify than the behavior is predictable

1.Empty Linked list
2.Linked list w.o any duplicated
3. LL with duplicated of the first elem
4. LL such that every node has a duplicate
5. LL such that first and last node has duplicate
6. Very Big linked list with no duplicate

linked list with loop

import java.lang.*;

import java.util.*;

import java.io.*;



class SLinkedCircularList

{

private int data;

private SLinkedCircularList next;





public SLinkedCircularList()

{

data = 0;

next = this;

}



public SLinkedCircularList(int value)

{

data = value;

next = this;

}



public SLinkedCircularList InsertNext(int value)

{

SLinkedCircularList node = new SLinkedCircularList(value);

if (this.next == this) // only one node in the circular list

{

// Easy to handle, after the two lines of executions,

// there will be two nodes in the circular list

node.next = this;

this.next = node;

}

else

{

// Insert in the middle



SLinkedCircularList temp = this.next;

node.next = temp;

this.next = node;

}

return node;



}



public int DeleteNext()

{

if (this.next == this)

{

System.out.println("\nThe node can not be deleted as there is only one node in the circular list");

return 0;

}



SLinkedCircularList node = this.next;

this.next = this.next.next;

node = null;

return 1;

}



public void Traverse()

{

Traverse(this);

}



public void Traverse(SLinkedCircularList node)

{

if (node == null)

node = this;

System.out.println("\n\nTraversing in Forward Direction\n\n");

SLinkedCircularList startnode = node;



do

{

System.out.println(node.data);

node = node.next;

}

while (node != startnode);

}



public int GetNumberOfNodes()

{

return GetNumberOfNodes(this);

}



public int GetNumberOfNodes(SLinkedCircularList node)

{

if (node == null)

node = this;



int count = 0;

SLinkedCircularList startnode = node;

do

{

count++;

node = node.next;

}

while (node != startnode);



System.out.println("\nCurrent Node Value: " + node.data);

System.out.println("\nTotal nodes in Circular List: " + count);



return count;

}



public static void main(String[] args)

{



SLinkedCircularList node1 = new SLinkedCircularList(1);

node1.DeleteNext(); // Delete will fail in this case.



SLinkedCircularList node2 = node1.InsertNext(2);

node1.DeleteNext(); // It will delete the node2.



node2 = node1.InsertNext(2); // Insert it again



SLinkedCircularList node3 = node2.InsertNext(3);

SLinkedCircularList node4 = node3.InsertNext(4);

SLinkedCircularList node5 = node4.InsertNext(5);



node1.GetNumberOfNodes();

node3.GetNumberOfNodes();

node5.GetNumberOfNodes();



node1.Traverse();

node3.DeleteNext(); // delete the node "4"

node2.Traverse();



node1.GetNumberOfNodes();

node3.GetNumberOfNodes();

node5.GetNumberOfNodes();

}

}