This chapter is from the book
This chapter is from the book
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
What are the empty and trivial cases for this function?
Because the main loop in the code is while(true), why is the function guaranteed to eventually exit?
How many different inputs are necessary to guarantee complete code coverage?
Hints
Walk through HasLoop() in the following cases:
The list has only one element, so head.next == null.
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.
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.