Home > Articles > Programming > Java

  • Print
  • + Share This
This chapter is from the book

Check if a List Has a Loop

This function checks if a singly linked list has a loop in it.

It uses the same ListNode and List classes from the previous examples, but implements a new member method, HasLoop(). A list has a loop if there is some ListNode node in it for which node.next is equal to head.

Source Code

1.  class List {
2. 
3.      private ListNode head;
4. 
5.      public List() {
6.          head = null;
7.     }
8. 
9.     public List(ListNode ln) {
10.         head = ln;
11.     }
12.
13.     public boolean HasLoop() {
14.
15.         //
16.         // The algorithm is to start two pointers
17.         // at the head of the list; as the first pointer
18.         // advances one element in the list, the second
19.         // advances by two elements. If the second
20.         // pointer hits a null next pointer, then the
21.         // list does not have a loop; if the second
22.         // pointer hits the first pointer, then the list
23.         // has a loop.
24.         //
25.
26.         ListNode ln1, ln2;
27.
28.         if ((head == null) || (head.next == null))
29.             return false;
30.
31.         ln1 = head;
32.         ln2 = head.next;
33.
34.         while (true) {
35.             
36.             if (ln1 == ln2)
37.                 return true;
38.
39.             if (ln1.next == null)
40.                 return false;
41.             else
42.                 ln1 = ln1.next;
43.
44.             if (ln1 == ln2)
45.                 return true;
46.
47.             if (ln2.next == null)
48.                 return false;
49.             else
50.                 ln2 = ln2.next;
51.
52.             if (ln1 == ln2)
53. return true;
54.
55.             if (ln2.next == null)
56.                 return false;
57.             else
58.                 ln2 = ln2.next;
59.
60.         }
61.     }

Suggestions

  1. What are the empty and trivial cases for this function?

  2. Because the main loop in the code is while(true), why is the function guaranteed to eventually exit?

  3. How many different inputs are necessary to guarantee complete code coverage?

Hints

Walk through HasLoop() in the following cases:

  1. The list has only one element, so head.next == null.

  2. The list has three elements, so head points to Node1, Node1.next points to Node2, Node2.next points to Node3, and Node3.next is null.

  3. The list has a loop, where head points to Node1, Node1.next points to Node2, and Node2.next points to head.

Explanation of the Bug

The code returns true, which indicates that it has found a loop, on any list with more than one element. The reason is that the check on lines 44–45, immediately after advancing ln1

    if (ln1 == ln2)
        return true;

is true when ln1 is advanced from the first to the second element in the list. This is because ln2 is initialized before the loop to point to the second element, and it has not moved yet.

In fact, the check is unnecessary because the code is concerned with ln2 looping around and catching up to ln1, so there is no need to check for equality after ln1 advances. This is an F.location error because the two lines should not exist at all.

  • + Share This
  • 🔖 Save To Your Account