Find loop starting point in a circular linked list

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
Circular linked list:
A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

My initial thoughts:
Initialize with two pointers to the head, the slow pointer and fast pointer. Each time, slow pointer moves one step while the fast pointer moves two steps. If they meet in the some point, then that node must be the starting point of the loop.

My initial codes:

	public static LLNode findLoopBeginningPoint(
			LLNode head) {
		LLNode slowPointer = head;
		LLNode fastPointer = head;

		fastPointer = fastPointer.getNext();
		fastPointer = fastPointer.getNext();

		while (slowPointer != fastPointer) {
			slowPointer = slowPointer.getNext();
			fastPointer = fastPointer.getNext();
			fastPointer = fastPointer.getNext();
		}

		return slowPointer;
	}

Comments after running:
The testing input yields out ‘E’ instead of the expected result ‘C’. Walk through the code:

  • fastPointer: ‘C’; slowPointer: ‘A’
  • fastPointer: ‘E’; slowPointer: ‘B’
  • fastPointer: ‘D’; slowPointer: ‘C’
  • fastPointer: ‘C’; slowPointer: ‘D’
  • fastPointer: ‘E’; slowPointer: ‘E’

The catch point of this algorithm is that when the fast pointer meets the slow pointer, the distance between their meeting point and the starting point of the loop, is equal to the distance between the head of the list and the starting point of the loop.
Let us denote the length of non-loop list as m, i.e., the distance between the head of the list to the starting point of the loop is m. Let’s also have the size of the loop as L. When the two pointer meets, let us denote the distance between the meeting point of the starting of the loop as d. So, at the time of their meet, the fast pointer would have travelled m+nL-d and the slow pointer only travelled m+L-d. Therefore we have m+nL-d=2(m+L-d) \Leftrightarrow d\equiv m \pmod L.
Therefore, when the two pointer meets, we can move one pointer to the head, and then move them one step at each time, when they meet again, they will meet at the starting pointer of the loop.

	public static LLNode<Character> findLoopBeginningPoint(
			LLNode<Character> head) {
		LLNode<Character> slowPointer = head;
		LLNode<Character> fastPointer = head;

		do {
			slowPointer = slowPointer.getNext();
			fastPointer = fastPointer.getNext().getNext();
		} while (slowPointer != fastPointer);

		if (slowPointer == null)
			return null;

		slowPointer = head;
		while (slowPointer != fastPointer) {
			slowPointer = slowPointer.getNext();
			fastPointer = fastPointer.getNext();
		}

		return slowPointer;
	}

Comments after running
If the linked list has no loop, the highlighted line will raise an null-pointer exception under some circumstances.

Solution

	public static LLNode<Character> FindBeginning(LLNode<Character> head) {
		LLNode<Character> n1 = head;
		LLNode<Character> n2 = head;

		// find meeting point
		while (n2.getNext() != null) {
			n1 = n1.getNext();
			n2 = n2.getNext().getNext();
			if (n1 == n2)
				break;
		}

		// Error check - there is no meeting point, and therefore no loop
		if (n2.getNext() == null)
			return null;

		/*
		 * Move n1 to Head. Keep n2 at Meeting Point. Each are k steps from the
		 * Loop Start. If they move at the same pace, they must meet at Loop
		 * Start.
		 */
		n1 = head;
		while (n1 != n2) {
			n1 = n1.getNext();
			n2 = n2.getNext();
		}

		return n2;
	}
Advertisements

2 Comments (+add yours?)

  1. priyal
    Nov 04, 2012 @ 18:55:37

    how would you do this using c??

    Reply

  2. kinshuk4
    May 09, 2014 @ 04:18:46

    Your blog is really great, look for any post and you find it. Here is my similar post :
    http://k2code.blogspot.in/2011/12/finding-start-of-loop-in-circular.html

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: