Archive for the ‘computer science’ Category

Solution for singly-circularly-linked problem

June 10, 2007

I promised to post a solution for the problem I set earlier. Now it’s time to keep the promise.

The solution is really simple because the problem itself is trivial I would say. Imagine two racers at the running track that has circular shape both starting from the same position. Let’s assume that one trained harder and can run at double speed of the another racer. Let’s imagine that they start to race but do not finish after running a one lap. They continue to race, what will happen eventually? The answer is that faster one will lap the slower runner. That’s main idea behind the solution… 🙂

Let’s translate it to a terms used in programming. You have two variables (runners) pointing at the first element of the list. Now, each time one pointer moves two elements further but other one moves only by one element from the list further. You can observe the process at this picture:

Picture showing two pointer moving along the list

Now we have two cases:

  1. If list is not circularly-linked faster runner (pointer) will reach its end and that will be a sign for us that we have detected list that is not circularly-linked
  2. If list has a cycle faster runner (pointer) will lap the slower one at some point and that will be an information for the algorithm that circularly-linked list has been detected

Obviously, the algorithm uses constant memory (two pointers). I’ll leave as an exercise to show that number of pointer shifts is not great than 2n where n is number of elements in the list.

Here you have simple implementation of this algorithm:

public class DetectCycle {

	static int steps = 0;
	
	public static void main(String[] args) {
		System.out.println(detectCycle(createLinkedList(50, -1)));
		System.out.println(steps);
	}
	
	static private boolean detectCycle(ListItem head) {
		ListItem slowerRunner = head;
		ListItem fasterRunner = head;
		steps = 0;
		while (true) {
			if (fasterRunner.getNext() == null) return false;
			fasterRunner = fasterRunner.getNext();
			if (fasterRunner.equals(slowerRunner)) return true;
			
			if (fasterRunner.getNext() == null) return false;
			fasterRunner = fasterRunner.getNext();
			if (fasterRunner.equals(slowerRunner)) return true;
			
			slowerRunner = slowerRunner.getNext();
			steps = steps + 2;
		}
	}
	
	static private ListItem createLinkedList(int numberOfItems, 
                                                 int closeCycleAtPosition) {
		ListItem head = new ListItem();
		ListItem tail = head;
		
		for (int i = 1; i <= numberOfItems; i++) {
			tail.setNext(new ListItem());
			tail = tail.getNext();
		}
		
		if (closeCycleAtPosition >= 0) {
			ListItem item = head;
			for (int i = 1; i < closeCycleAtPosition; i++)
				item = item.getNext();
			tail.setNext(item); //closing cycle at specified position
		}
		
		return head;
	}

}

and ListItem class:

public class ListItem {
	private ListItem next;
	
	public ListItem() {
		next = null;
	}
	
	public ListItem getNext() {
		return next;
	}
	
	void setNext(ListItem next) {
		this.next = next;
	}
}

EDIT: I thought that it would be nice to tell you similar riddle. Here it goes:
How to count number of elements (legnth) of the list despite it has cycle or not. Rules are the same: algorithm must be linear and use constant amount of memory. Again solution is simple!

Advertisements

Is list singly-circularly-linked list problem

March 19, 2007

Hi, it’s my first post on the blog ever! 🙂

To not bore you telling how excited I am having my own blog I would like to give you some food for thought. You should be also warned: on this blog it’s going to be much more this kind of stuff as I’m math student of MIMUW. Yes, that famous and unbeatable university 😉

Ok, let’s move to the problem that my colleague (Paweł) told me about today. There is an singly-linked list and we are given one of the nodes it consists of.
The problem: how to determine in O(n) time and O(1) memory if this list is singly-circularly-linked list or not. In other words: does the list have a cycle? O(n) means that your algorithm must be linear when it comes to the number of elementary operations and can modify only constant amount of memory. That means you cannot mark particular node if it was visited or not.

In order to avoid confusion I’ve created drawing illustrating valid list:list.png

Ok, I promise to not use OpenOffice.org Draw and produce nicer image next time.