Need help writing a SimpleNode class and possibly reverse() method. Specs below

Question

Need help writing a SimpleNode class and possibly reverse() method. Specs below

SimpleNode is a (non-generic) representation of a Node class applied for linked list implementations. None of the standard methods except for the constructor will be used in this demonstration. You will need however the toString( ) method and the getTail( ) method from your previous assignments. The type of the data stored in the nodes has no relevance to this application, choose String values at will. I will also give my current code, I just do not know if it is correct...

-----------------------------------------------------------------------------------

current code:

public class SimpleNode<E> {
  
// Invariant of the Node class:
// 1. Each node has one reference to an E Object, stored in the instance
// variable data.
// 2. For the final node of a list, the link part is null.
// Otherwise, the link part is a reference to the
// next node of the list.
private String data;
private SimpleNode<E> link;

public SimpleNode(String data, SimpleNode<E> link){
this.data = data;
this.link = link;
}

public static <E> SimpleNode<E> getTail(SimpleNode<E> source){

SimpleNode<E> tail = source;

if (tail == null){
return null;
  
}
while (tail.link != null)
{
tail = tail.link;

}
return tail;

}   

public String toString( int count){
  
String field1 = "";
String field2 = "";
  
if(data == null)
field1 = "dummy";
else
field1 = data.toString();
  
if(link == null)
field2 = "null in tail";
else
field2 = data.toString();
  
return field1+", "+field2;
  
}
  
}

-----------------------------------------------------------------------------------------------

Just for better clarification, this class will implement a method named reverse(). specifications are below

This method:

-- is static

-- takes the head of the original list for parameter

-- given the head reference of a linked list, returns the head reference of the linked list in reversed order; that is the method has to reverse all the links of the original list, the original tail will be the head and the original head will be the new tail. Note that the nodes are not cloned and the data stored in the nodes are not moved or changed

must be recursive, applied on shorter and shorter lists

Any help with the SimpleNode class or the reverse() method is greatly appreciated

Explanation / Answer

As per requirement we have understood that you need to implement reverse() method which will reverse the linked list

Here is the working code for the same-

/* * Reverse a singly linked list using recursion. In recursion Stack is * used to store data. *
   * 1. Traverse linked list till we find the tail, * that would be new head for reversed linked list. */
     
   public static SimpleNode reverseList(SimpleNode head) {
       if(head==null || head.link == null)   //if list is empty or contain only one node then return that node
       return head;
         
       //get second node
       SimpleNode second = head.link;   //get link node after head
       //set first's link to be null
       head.link = null;  
         
       SimpleNode rest = reverseList(second);   //now again reverse list from second node onwards.
       second.link = head;   // shift head to second's link
         
       return rest;
       }

//Note: the above-mentioned code is tested and working fine.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.