I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Does the Linked List Have a Circular Reference?

01.10.2013
| 4984 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Determine if there is a circular reference in a linked list

Given a single linked list, write a method that will determine if the "next" pointer of one of the nodes is pointing to a previous node in your list.


Catch up on all our previous puzzlers here.

Comments

Vijay Nathani replied on Thu, 2013/01/10 - 4:21am

The problem does not specify whether to use logical equals or identity equal. So both solution in groovy are:

def isCircularWithEquals(listToCheck) {
	new HashSet(listToCheck).size() != listToCheck.size()
}
def isCircularWithIdentity(listToCheck) {
	def items = new com.google.common.collect.HashMultiset()
	listToCheck.findResult(false) { n -> 
		def r = items.find { it.is(n) }
		items.add(n)
		r
	}
}
assert !isCircularWithEquals([1,2,3])
assert isCircularWithEquals([1,2,new Integer(1),3])
assert !isCircularWithIdentity([1,2,3])
assert isCircularWithIdentity([1,2,1,3])

Eric Jablow replied on Thu, 2013/01/10 - 12:45pm

The cheapest way to do this is the baby-step/giant-step algorithm. In pseudo-code, it's:

  1. Given a list, L,
  2. Get an iterator for L, b.
  3. Get a second iterator for L, g.
  4. Advance b.
    1. If b is at the end of the list, return false.
  5. Advance g.
    1. If g is at the end of the list, return false.
  6. Advance g again.
    1. If g is at the end of the list, return false.
  7. If b and g point to the same node, return true.
  8. Go to step 4.
If the list is eventually circular, b and g will eventually enter a loop. And since g traversers the loop twice as fast as b, they will eventually meet. Overhead storage is fixed here.


Gonzalo Arrivi replied on Wed, 2013/01/16 - 9:09am

A not tested response:


// This test implementation of a Linked List
public class MyLinkedList{
	public MyLinkedList next;
	public int value;
}

// Method to discover circular references on a linked list
public bool existsCircularReference(MyLinkedList linkedList){

	////// Variable declaration section
	MyLinkedList currentItem, nextItem;
	HashTable visitedNodes;

	// Create a new hashmap to know the visited nodes
	visitedNodesMap = new HashMap();
	
	// Set the parameter as the nextItem to test
	nextItem = linkedList;

	// While the 
	while(nextItem != null && !visitedNodesMap.containsKey(nextItem)){
		// The next item becomes the current one
		currentItem = nextItem;

		// The current element is added into the visited items hashmap (no value needed)
		visitedNodesMap.put(currentItem, null);
	
		// The next element is set
		nextItem = currentItem.next;
	}

	// If there are still elements in the list, there is a Circular reference
	return nextItem != null;
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.