This chapter is from the book
This chapter is from the book
This chapter is from the book
Reverse a Linked List
This function reverses a singly linked list by walking the list and changing pointers.
Each element in the list is an instance of a class ListNode. The list itself is an instance of a class List. ListNode has a next member that points to the next element on the list. The final element on the list has a next pointer equal to null.
List has a method called Reverse(), which is the method to reverse the linked list.
Source Code
1. class ListNode {
2.
3. private int value;
4. protected ListNode next;
5.
6. public ListNode(int v) {
7. value = v;
8. next = null;
9. }
10.
11. public ListNode(int v, ListNode n) {
12. value = v;
13. next = n;
14. }
15.
16. public int getValue() { return value; }
17.
18. }
19.
20. class List {
21.
22. private ListNode head;
23.
24. public List() {
25. head = null;
26. }
27.
28. public List(ListNode ln) {
29. head = ln;
30. }
31.
32. public void Reverse() {
33.
34. // Walk the list, reversing the direction of
35. // the next pointers.
36.
37. ListNode ln1, ln2, ln3, ln4;
38.
39. if (head == null)
40. return;
41.
42. ln1 = head;
43. ln2 = head.next;
44. ln3 = null;
45.
46. while (ln2 != null) {
47. ln4 = ln2.next;
48. ln1.next = ln3;
49. ln3 = ln1;
50. ln1 = ln2;
51. ln2 = ln4;
52. }
53.
54. //
55. // When we get to the end of the list, the last
56. // element we looked at is the new head.
57. //
58.
59. head = ln1;
60. }
61. }
Suggestions
What are the empty and trivial cases for the Reverse() method? How will the code handle them?
What is the purpose of the variable ln4?
Describe the meaning of ln1, ln2, and ln3 after the while loop ends. Is the comment on lines 54–57 correct?
Hints
Walk through Reverse() 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.
Explanation of the Bug
The code on line 59 is correct. The value of ln1 after the last iteration of the while() loop is the new head of the list. However, the next pointer of that element is still null because it used to be the end of the list.
In the somewhat-confusing nomenclature of this function, ln3 is the element that used to be before ln1 in the list, so to finish off the reversal, there needs to be a line added after line 59 that reads as follows:
ln1.next = ln3;
This is a D.limit error because the code works correctly except when handling the last element of the old list. The effect of the bug is that the last element of the old list keeps its next pointer as null. Since this element becomes the first element of the new list, this truncates the list to a single element.