Question

Write a method in class SLL<T> called public static SLL<T> reverse() that produces a new linked list with the contents of the original list reversed. Make sure not to use any methods like addToHead() or addToTail(). In addition, consider any special cases that might arise.

(b) What is the big-O complexity of your method in terms of the list size n.

Answer 1

You have not provided the code for SLL class. However assuming it has a nested Node class for single linked list with data and next variables inside it, the following code will work.

public static SLL<T> reverse()
{
   SLL<T> rev = new SLL<T>();
   Node n = head;
   Node prev = null;
   Node newHead = null;
   while(n != null){
       newHead = new Node(n.data);
       newHead.next = prev;
       prev = newHead;
       n = n.next;
   }
  
   rev.head = newHead;
   return rev;
}

The time complexity of above algorithm is O(n)