I spent a considerable amount of time over the weekend experimenting with this easy challenge from HackerRank. If interested you can get to the challenge using the following URL: https://www.hackerrank.com/challenges/ctci-linked-list-cycle
For starters, the first element in the list is also the head. This is not a good idea. The reason is that if the head changes references to the list are lost. This might be OK for trivial examples, but in real life a list may be referenced by different threads.
It seems to me that the challenge addresses a possible issue when a person implements their own liked list. It is hard to create a cycle with a list that has methods to add and remove elements. IN that case the links are managed by the class. A cycle condition would be due to a poor implementation that was not tested.
If you are using Java and a list class from the library, I do not see how a cycle could be created. If you have an example I would like to hear from you.
The first reason I spent a lot of time on this challenge was to make sure the requirements are meant not to practice on a condition that would never be encountered; at least not in an OOP language (e.g., Java), but to verify the mental thinking process of an individual.
The second reason, and perhaps the most important to me, is that some time ago I designed and implemented a queue library with an API that has been used in several commercial of the shelf (COTS) products. I am not at liberty to show the code, but the API is public domain. A partial edited listing of the API description (sncrque.h) follows:
typedef struct SENCOR_QUEUE {
struct SENCOR_QUEUE *next;
struct SENCOR_QUEUE *prev;
unsigned long count;
unsigned long priority;
unsigned long mutex;
__int32 time;
unsigned long signature;
void *privateData;
unsigned long elementSize;
unsigned long maxCount;
unsigned char filler[SENCOR_QUEUE_LEN – 40];
} SENCOR_QUEUE;
SENCOR_EXPORT INT_CALL QueAlloc ( SENCOR_QUEUE **queue
);
SENCOR_EXPORT INT_CALL QueAppend (
SENCOR_QUEUE *baseQueue, SENCOR_QUEUE *queueToAppend
);
SENCOR_EXPORT INT_CALL QueClear (
SENCOR_QUEUE *queue
);
SENCOR_EXPORT INT_CALL QueClone (
SENCOR_QUEUE *originalQ,
unsigned long elementSize,
SENCOR_QUEUE *cloneQ
);
SENCOR_EXPORT INT_CALL QueConsistent (
SENCOR_QUEUE *queue
);
SENCOR_EXPORT INT_CALL QueCopy (
SENCOR_QUEUE *dstQueue,
SENCOR_QUEUE *srcQueue
);
SENCOR_EXPORT INT_CALL QueCopyCount (
SENCOR_QUEUE *srcQueue,
SENCOR_QUEUE *dstQueue,
unsigned long countToCopy
);
SENCOR_EXPORT INT_CALL QueCopyFromHere (
SENCOR_QUEUE *srcQueue,
SENCOR_QUEUE *element,
SENCOR_QUEUE *dstQueue
);
SENCOR_EXPORT INT_CALL QueCopyThis (
SENCOR_QUEUE *srcQueue,
SENCOR_QUEUE *dstQueue,
int n
);
SENCOR_EXPORT INT_CALL QueDeQueue (
SENCOR_QUEUE *queue,
SENCOR_QUEUE *element
);
SENCOR_EXPORT INT_CALL QueDestroy (
SENCOR_QUEUE *queue
);
SENCOR_EXPORT INT_CALL QueDump (
SENCOR_QUEUE *queue
);
SENCOR_EXPORT INT_CALL QueFree (
SENCOR_QUEUE **queue
);
SENCOR_EXPORT INT_CALL QueGetCount (
SENCOR_QUEUE *queue,
unsigned long *count
);
SENCOR_EXPORT INT_CALL QueGetElementSize (
SENCOR_QUEUE *queue,
unsigned long *elementSize
);
SENCOR_EXPORT INT_CALL QueGetMaxCount (
SENCOR_QUEUE *queue,
unsigned long *maxCount
);
SENCOR_EXPORT INT_CALL QueGetPrivateData (
SENCOR_QUEUE *queue,
void **privateData
);
SENCOR_EXPORT INT_CALL QueGetTime (
SENCOR_QUEUE *queue,
time_t *time
);
SENCOR_EXPORT INT_CALL QueHasCycle (
SENCOR_QUEUE *queue,
BOOL *hasCycle
);
SENCOR_EXPORT INT_CALL QueInit (
SENCOR_QUEUE *queue
);
SENCOR_EXPORT INT_CALL QueInsert (
SENCOR_QUEUE *queue,
SENCOR_QUEUE *element
);
SENCOR_EXPORT INT_CALL QueInsertHead (
SENCOR_QUEUE *queue,
SENCOR_QUEUE *element
);
SENCOR_EXPORT INT_CALL QueInsertHere (
SENCOR_QUEUE *queue,
SENCOR_QUEUE *here,
unsigned short position,
SENCOR_QUEUE *element
);
SENCOR_EXPORT INT_CALL QueIsEmpty (
SENCOR_QUEUE *queue,
BOOL *isEmpty
);
SENCOR_EXPORT INT_CALL QueIsFull (
SENCOR_QUEUE *queue,
BOOL *isFull
);
SENCOR_EXPORT INT_CALL QueMoveElement (
SENCOR_QUEUE *srcQueue,
SENCOR_QUEUE *element,
SENCOR_QUEUE *dstQueue
);
SENCOR_EXPORT INT_CALL QuePack (
SENCOR_QUEUE *queue,
unsigned long elementSize,
void **buffer,
unsigned long *bufferSize
);
SENCOR_EXPORT INT_CALL QuePointToElement (
SENCOR_QUEUE *queue,
unsigned long n,
SENCOR_QUEUE **element
);
SENCOR_EXPORT INT_CALL QueRemove (
SENCOR_QUEUE *queue,
SENCOR_QUEUE **element
);
SENCOR_EXPORT INT_CALL QueSetElementSize (
SENCOR_QUEUE *queue,
unsigned long elementSize
);
SENCOR_EXPORT INT_CALL QueSetMaxCount (
SENCOR_QUEUE *queue,
unsigned long maxCount
);
SENCOR_EXPORT INT_CALL QueSetPrivateData (
SENCOR_QUEUE *queue,
void *privateData
);
SENCOR_EXPORT INT_CALL QueSetTime (
SENCOR_QUEUE *queue,
time_t time
);
SENCOR_EXPORT INT_CALL QueTimeDiff (
SENCOR_QUEUE *element,
time_t *seconds
);
SENCOR_EXPORT INT_CALL QueUnPack (
void *buffer,
unsigned long bufferSize,
unsigned long elementSize,
SENCOR_QUEUE *queue
);
SENCOR_EXPORT int __cdecl SencorQueueCompare (
const void *a,
const void *b
);
As I mentioned earlier, if the functions / methods are working properly then it is quite difficult to end up with a circular queue. Keep in mind that the methods manage all pointers. In addition an empty queue is instantiated with its own set of pointers. The head and tail are set to point to the queue element when the queue is created and is empty. There are simple consistencies checks perform when each method is invoked.
After solving this challenge I decided to add the QueHasCycle() method. In a nutshell the method performs the following set of steps:
// **** initialization ****
// **** perform some sanity checks ****
// **** check if the queue has been initialized ****
// **** check if queue is empty ****
// **** check if count is too big ****
// **** allocate array of links ****
// **** traverse the queue using the next link ****
// **** sort the links ****
// **** check for duplicates ****
// **** traverse the queue using the prev link ****
// **** sort the links ****
// **** check for duplicates ****
// **** clean up ****
// **** free array of links (if needed) ****
// **** inform the user what is going on ****
// **** inform the caller what went on ****
Given that this new method will be part of the standard API from now on, I decided not to include its code.
I always start a method with initialization steps and always terminate with a clean up. An array of pointers is allocated. The array is populated by traversing the queue from the head to the tail using the next pointer. Each time an element is visited the value of the pointer is stored in the array. The array of pointers is sorted. The array is traversed looking for duplicates. A dup0licate would indicate a circular list.
The traversal operation is then repeated using the prev pointer.
The actual code was implemented using the Visual Studio 2013 Professional edition.
I will now show a simple example using a test utility. I always develop test 
code (which fails) and then implement the actual methods. In the way additional tests or code modifications may occur. Such process is quite common in software development. Some edited (for duplication) console screen captures follow:
Edited main menu for queue testing:
* * * * Test Queue Methods * * * *
1 QueAlloc() heap (used in most cases)
2 QueInit() stack
3 QueClear()
4 QueFree() heap
5 QueDestroy() stack
6 QueInsert()
7 QuePush()
8 QuePop()
9 QueDump()
10 QueConsistent()
11 QueCopy()
12 QueDeQueue()
13 QueGetCount()
14 QueInsertHead()
15 QueInsertHere()
16 QueIsEmpty()
17 QueRemove()
18 QueTimeDiff()
19 QueMutexLock()
20 QueMutexIsLocked()
21 QuePointToElement()
22 QuePack() <—+
23 QueUnPack() <—+
24 QueAppend()
25 DupOrSeq
26 QueIsFull()
27 QueSetMaxCount()
28 QueGetMaxCount()
29 QueHasCycle()
-1 QUIT
>>> selection [1]:
After allocating a queue:
>>> selection [1]: 16
TestQueCalls <<< QueIsEmpty isEmpty: 1 (bool) line: 1518
>>> selection [16]: 9
QueDump <<< sizeof(SENCOR_QUEUE): 64
QueDump <<< queue: 0x011c1920 line: 1695
+———————-+
+–>| queue: 011c1920|<——-+
| | count: 0| |
| | priority: 0| |
| | time: 58a1c5c7| |
| | signature: abcddcba| |
| | elementSize: 0| |
| | privateData: 00000000+–> |
+—+ prev: 011c1920| |
| next: 011c1920+——–+
+———————-+
After setting the maximum queue size to 3 and attempting to enter 4 elements:
>>> selection [6]: 6
>>> element priority [0]:
>>> element value [34]: 44
QueInsert <<< queue->count: 3 >= queue->maxCount: 3 line: 694 file ==>c:\sencorsource\source\que.c<==
Message <<< Buffer is FULL – WAR_BUFFER_FULL
TestQueInsert <<< QueInsert status: -1359 line: 1733 file ==>c:\sencorsource\source\testlib.c<==
TestQueCalls <<< TestQueInsert status: -1359
>>> selection [6]: 9
TestQueDump <<< element: 0x011c17d0 priority: 0 value: 11
TestQueDump <<< element: 0x011c1990 priority: 0 value: 22
TestQueDump <<< element: 0x011c1a00 priority: 0 value: 33
QueDump <<< sizeof(SENCOR_QUEUE): 64
QueDump <<< queue: 0x011c1920 line: 1695
+———————-+
| queue: 011c1920|<——-+
| count: 3| |
| priority: 0| |
| time: 58a1c5c7| |
| signature: abcddcba| |
| elementSize: 0| |
| privateData: 00000000+–> |
+——+ prev: 011c1a00| |
| +–>| next: 011c17d0+—–+ |
| | +———————-+ | |
| | | |
| | +——————+ | |
| | | element: 011c17d0|<——–+ |
| +—+ prev: 011c1920| |
| +–>| next: 011c1990+———+ |
| | +——————+ | |
| | | |
| | +——————+ | |
| | | element: 011c1990|<——–+ |
| +—+ prev: 011c17d0| |
| +–>| next: 011c1a00+———+ |
| | +——————+ | |
| | | |
| | +——————+ | |
| | | element: 011c1a00|<——–+ |
| +—+ prev: 011c1990| |
+—–>| next: 011c1920+————+
+——————+
Three elements with values 11, 22 and 33 have been inserted. When I tried inserting element 44 the operation failed indicating the queue was full. A simplified graphical representation was then invoked.
I then invoked the new QueHasCycle() method:
>>> selection [9]: 29
TestQueCalls <<< QueHasCycle hasCycle: 0 (bool) line: 1603
As expected, the queue has no cycles.
Note that the API includes a QueConsistent() method which perform a set of consistency checks. The QueHasCycle() method is not included at this time.
>>> selection [29]: 10
Getting back to the challenge, following is the Java code implemented using the Eclipse IDE:
import java.util.Random;
import java.util.Scanner;
class Node {
// **** constants ****
public final int MAX_SIZE = 100;
public final int CYCLE_MOD = 7;
// **** members ****
int data;
Node next;
/*
* constructor
*/
public Node(int data) {
this.data = data;
this.next = null;
}
/*
* append node to list
*/
Node append(Node head, int data) {
// **** instantiate new node ****
Node node = new Node(data);
// **** empty list (new head) ****
if (head == null) {
return node;
}
// **** get to the last node ****
Node p = head;
for ( ; p.next != null; p = p.next) {}
// **** append new node to list ****
p.next = node;
// **** return head of list ****
return head;
}
void makeItCycle(Node head) {
System.out.println(“makeItCycle <<< entering …”);
// **** check for null head ****
if (head == null) {
return;
}
// **** generate random place to put cycle ****
Random rand = new Random(System.currentTimeMillis());
int c = 1 + rand.nextInt(CYCLE_MOD – 1);
System.out.println(“makeItCycle <<< c: ” + c);
// **** get to the tail ****
Node cycle = null;
Node p = head;
for (int i = 1; p.next != null; p = p.next, i++) {
if (c == i) {
System.out.println(“makeItCycle <<< cycling …”);
cycle = p;
}
}
// **** ****
p.next = cycle;
}
void show(Node head) {
// **** special case ****
if (head == null) {
System.out.println(“show <<< list: null”);
return;
}
// **** traverse list ****
System.out.print(“show <<< list: “);
int i = 0;
for (Node node = head; (node != null) && (i <= MAX_SIZE); node = node.next, i++) {
System.out.print(node.data + ” “);
}
System.out.println();
}
}
public class Solution {
static boolean hasCycle(Node head) {
// **** check for null head condition ****
if (head == null) {
return false;
}
// **** count nodes in the list ****
int count = 0;
for (Node p = head; (p != null) && (count < 100); p = p.next, count++) {}
// **** ****
return (count >= 100);
}
public static void main(String[] args) {
// **** instantiate an empty list ****
Node head = null;
// **** get number of elements ****
Scanner sc = new Scanner(System.in);
System.out.print(“main <<< N: “);
int N = sc.nextInt();
// **** close scanner ****
sc.close();
// **** start with a head node (if needed) ****
if (N > 0) {
// **** ****
head = new Node(1);
// **** check (update if needed) ****
if (N > head.MAX_SIZE) {
N = head.MAX_SIZE;
}
}
// **** loop building list ****
for (int i = 2; i <= N; i++) {
head = head.append(head, i);
}
// **** make list cycle (if needed) ****
if ((N != 0) && (N % head.CYCLE_MOD) == 0) {
head.makeItCycle(head);
}
// **** show the contents of the list ****
if (head != null) {
head.show(head);
}
// **** check if list has cycle ****
boolean cycle = hasCycle(head);
System.out.println(“main <<< cycle: ” + cycle);
// *** check if we do not have a cycle ****
if ((N != 0) && ((N % head.CYCLE_MOD) == 0)) {
if (!cycle) {
System.out.println(“main <<< should HAVE cycle !!!”);
}
}
}
}
Please note that the actual code for the solution is in the hasCycle() method. The rest of the code was used to experiment and test.
If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa