Please show the java code and pseudocode as well
Describe and implement a recursive algorithm for reversing a singly linked list L, so that the ordering of the nodes becomes opposite of what it was before. What is the running time of your algorithm on a list of n values? Provide both the growth function and BigOh complexity. Create a driver class to test your implementation.
Algorithm reverse(current, previous):
Node temp
if(current=tail)
current.setNext(previous)
temp<head
L.setHead(tail)
L.setTail(temp)
else
reverse(current.getNext(), current)
current.setNext(previous)
Recursive Algorithm to fimd running time and space usage:
Algorithm Max (A, m, n)
if A[n-1]>m
m <= A[n-1]
if n=1
return m
else
return Max(A, m, n-1)
JAVA CODE:
public class SinglyLinkedList {
private Node head; // Head is the first node in linked list
public void append(T data){
if(head == null){
head = new Node(data);
return;
}
tail().next = new Node(data);
}
private Node tail() {
Node tail = head;
// Find last element of linked list known as tail
while(tail.next != null){
tail = tail.next;
}
return tail;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
Node current = head;
while(current != null){
sb.append(current).append("-->");
current = current.next;
}
if(sb.length() >=3){
sb.delete(sb.length() - 3, sb.length());
// to remove --> from last node
}
return sb.toString();
}
/**
* Reverse linked list using 3 pointers approach in O(n) time
* It basically creates a new list by reversing direction, and
* subsequently insert the element at the start of the list.
*/
public void reverseIteratively() {
Node current = head;
Node previous = null;
Node forward = null;
// traversing linked list until there is no more element
while(current.next != null){
// Saving reference of next node, since we are changing current node
forward = current.next;
// Inserting node at start of new list
current.next = previous;
previous = current;
// Advancing to next node
current = forward;
}
head = current;
head.next = previous;
}
/*
* 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.
*/
private Node reverseRecursively(Node node){
Node newHead;
//base case - tail of original linked list
if((node.next == null)){
return node;
}
newHead = reverseRecursively(node.next);
//reverse the link e.g. C->D->null will be null
node.next.next = node;
node.next = null;
return newHead;
}
public void reverseRecursively(){
head = reverseRecursively(head);
}
private static class Node {
private Node next;
private T data;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
}
Test Class
/** * Java program to test code of reversing singly linked list in Java.
* This test class test both iterative and recursive solution. Since
* the same list is first reversed using loops, and then again using recursion.
* You can see that final output is same as original linked list.
public class SinglyLinkedListTest {
public static void main(String args[]) {
SinglyLinkedList linkedlist = getDefaultList();
System.out.println("linked list before reversing : " + linkedlist); linkedlist.reverseIteratively();
System.out.println("linked list after reversing : " + linkedlist); linkedlist.reverseRecursively();
System.out.println("linked list after reversing recursively: " + linkedlist);
}
private static SinglyLinkedList getDefaultList(){
SinglyLinkedList linkedlist = new SinglyLinkedList();
linkedlist.append("A"); linkedlist.append("B"); linkedlist.append("C"); linkedlist.append("D"); linkedlist.append("E"); linkedlist.append("F");
return linkedlist;
}
}
Output:
linked list before reversing :
A-->B-->C-->D-->E-->F linked list after reversing :
F-->E-->D-->C-->B-->A linked list after reversing
recursively: A-->B-->C-->D-->E-->F
Read more:
https://javarevisited.blogspot.com/2017/03/how-to-reverse-linked-list-in-java-using-iteration-and-recursion.html#ixzz6am4uFqy5
Get Answers For Free
Most questions answered within 1 hours.