### Detect loop in a linked list

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 &lt; 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 &lt; 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.