( Java ) Help find the problem of the code, I couldn\'t get the reverse list rig
ID: 3740764 • Letter: #
Question
( Java ) Help find the problem of the code, I couldn't get the reverse list right in my test
Here is the code:
private BasicLinkedList<T> ReverseListAuxiliary(Node curr, Node prev){
if (curr.next == null) {
head = curr;
/* Update next to prev node */
curr.next = prev;
return null;
}
/* Save curr.next node for recursive call */
Node next1 = curr.next;
/* and update next ..*/
curr.next = prev;
return new BasicLinkedList<T>().addToEnd((T)ReverseListAuxiliary(next1, curr));
}
public BasicLinkedList<T> getReverseList(){
return ReverseListAuxiliary(head, null);
}
}
Here is the test code:
@Test
public void basicLinkedLIstReverse() {
BasicLinkedList<String> list1 = new BasicLinkedList<String> ();
list1.addToEnd("Hello").addToEnd("World").addToEnd("Mike");
list1.getReverseList();
assertEquals("Mike", list1.getFirst());
assertEquals("Hello", list1.getLast());
}
Explanation / Answer
// Java program for reversing the Linked list
class BasicLinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
// A simple and tail recursive function to reverse
// a linked list. prev is passed as NULL initially.
Node ReverseListAuxiliary(Node curr, Node prev) {
/* If last node mark it head*/
if (curr.next == null) {
head = curr;
/* Update next to prev node */
curr.next = prev;
return null;
}
/* Save curr->next node for recursive call */
Node next1 = curr.next;
/* and update next ..*/
curr.next = prev;
ReverseListAuxiliary(next1, curr);
return head;
}
// prints content of double linked list
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args) {
BasicLinkedList list = new BasicLinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(7);
list.head.next.next.next.next.next.next.next = new Node(8);
System.out.println("Original Linked list ");
list.printList(head);
Node res = list.ReverseListAuxiliary(head, null);
System.out.println("");
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(res);
}
}
Output:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.