Yesterday (8 of June 2011) my colleague told me about a task that he was given on some interview. The task was to determine if linked list contains a loop. The algorithm had to consume as less memory as possible. That task sounded interesting but I had neither time nor physical ability to solve the task that day (I was deadly tired). Another thing is today morning. Going by shared taxi I remembered the task and invented a concept of a solution in couple of minutes.
The idea was the following: if we know that we are N steps from a head of the list then if there is a loop somewhere between the head and the current node then the loop length is not greater than N+1. So we can remember the current list node and do N+1 steps moving along the list comparing pointer to the remembered list node with a pointer to a next list node. If we notice that pointers are the same - we are in the loop.
The first implementation of the loop detection was:
1: static bool ListHasLoop1(MyListElement head)
2: {
3: MyListElement current = head;
4: int currentPos = 1;
5:
6: while (current.Next != null)
7: {
8: MyListElement tmp = current.Next;
9: for (int i = 0; i < currentPos; i++)
10: {
11: if (tmp == current)
12: {
13: return true;
14: }
15: tmp = tmp.Next;
16: if (tmp == null)
17: {
18: return false;
19: }
20: }
21:
22: current = current.Next;
23: currentPos++;
24: }
25:
26: return false;
27: }
But looking at the code I realized that nested for either detects a loop or moves currentPos steps further along the list. So it makes sense to use the final pointer instead of "returning back" and starting from a node next to the current node. The second implementation was:
1: static bool ListHasLoop2(MyListElement head)
2: {
3: MyListElement current = head;
4: int currentPos = 0;
5:
6: while (current.Next != null)
7: {
8: MyListElement loopDetector = current;
9: current = current.Next;
10: for (int i = 0; i < currentPos+1; i++)
11: {
12: if (current == loopDetector)
13: {
14: return true;
15: }
16: current = current.Next;
17: if (current == null)
18: {
19: return false;
20: }
21: }
22:
23: currentPos += currentPos + 1;
24: }
25:
26: return false;
27: }
To test my implementation I implemented simplest linked list
1: class MyListElement
2: {
3: int _value;
4: MyListElement _next;
5:
6: public MyListElement(int value)
7: {
8: this._value = value;
9: }
10:
11: public MyListElement Next
12: {
13: get
14: {
15: return _next;
16: }
17: set
18: {
19: _next = value;
20: }
21: }
22: }
To switch between the implementations to run unit tersts I introduced a primitive wrapper
1: internal static bool ListHasLoop(MyListElement head)
2: {
3: return ListHasLoop2(head);
4: }
Here are the unit tests
1: [TestFixture]
2: class Tests
3: {
4: [Test]
5: public void OneElementList()
6: {
7: MyListElement head = MyList.CreateListFromArray(new int[] { 1 });
8: Assert.IsFalse(Program.ListHasLoop(head));
9: }
10:
11: [Test]
12: public void OneElementListWithLoop()
13: {
14: MyListElement head = MyList.CreateListFromArray(new int[] { 1 });
15: head.Next = head;
16:
17: Assert.IsTrue(Program.ListHasLoop(head));
18: }
19:
20: [Test]
21: public void TwoElementsList()
22: {
23: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2 });
24: Assert.IsFalse(Program.ListHasLoop(head));
25: }
26:
27: [Test]
28: public void TwoElementsListWithLoopToFirst()
29: {
30: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2 });
31: MyListElement second = MyList.GetElement(head, 1);
32: second.Next = head;
33:
34: Assert.IsTrue(Program.ListHasLoop(head));
35: }
36:
37: [Test]
38: public void TwoElementsListWithLoopToSecond()
39: {
40: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2 });
41: MyListElement second = MyList.GetElement(head, 1);
42: second.Next = second;
43:
44: Assert.IsTrue(Program.ListHasLoop(head));
45: }
46:
47: [Test]
48: public void ThreeElementsList()
49: {
50: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2, 3 });
51: Assert.IsFalse(Program.ListHasLoop(head));
52: }
53:
54: [Test]
55: public void ThreeElementsListWithLoopToFirst()
56: {
57: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2, 3 });
58: MyListElement last = MyList.GetElement(head, 2);
59: last.Next = head;
60:
61: Assert.IsTrue(Program.ListHasLoop(head));
62: }
63:
64: [Test]
65: public void ThreeElementsListWithLoopToSecond()
66: {
67: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2, 3 });
68: MyListElement last = MyList.GetElement(head, 2);
69: last.Next = MyList.GetElement(head, 1);
70:
71: Assert.IsTrue(Program.ListHasLoop(head));
72: }
73:
74: [Test]
75: public void ThreeElementsListWithLoopToThird()
76: {
77: MyListElement head = MyList.CreateListFromArray(new int[] { 1, 2, 3 });
78: MyListElement last = MyList.GetElement(head, 2);
79: last.Next = last;
80:
81: Assert.IsTrue(Program.ListHasLoop(head));
82: }
83: }
P.S.
After writing this article I searched the Internet for existing solutions. And found that my second attempt is an implementation of
Brent's algorithm.