Reverse a linked list
Example :
Input : 1->2->3
Output 3->2->1
Implementation
class ReverseLinkedListEx{
//Tree
static class Node{
int data;
Node next = null;
public Node(int data){
this.data = data;
}
//Utility to create a list
public void insert(int data){
Node newNode = new Node(data);
Node n = this;
if(n == null)
n = newNode;
while(n.next != null){
n = n.next;
}
n.next = newNode;
}
//function to reverse the given list
public Node reverse(Node head){
Node previous = null;
Node current = head;
Node forward;
while(current !=null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public void display(){
Node head = this;
if(head == null)
return;
while(head != null){
System.out.println(head.data);
head = head.next;
}
}
}
public static void main(String[] args){
Node root = new Node(1);
root.insert(2);
root.insert(3);
System.out.println("Reversed list :");
Node rev = root.reverse(root);
rev.display();
}
}
Output: 3->2->1
Time Complexity : O(N)
Space Complexity : O(1)
Example :
Input : 1->2->3
Output 3->2->1
Implementation
class ReverseLinkedListEx{
//Tree
static class Node{
int data;
Node next = null;
public Node(int data){
this.data = data;
}
//Utility to create a list
public void insert(int data){
Node newNode = new Node(data);
Node n = this;
if(n == null)
n = newNode;
while(n.next != null){
n = n.next;
}
n.next = newNode;
}
//function to reverse the given list
public Node reverse(Node head){
Node previous = null;
Node current = head;
Node forward;
while(current !=null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public void display(){
Node head = this;
if(head == null)
return;
while(head != null){
System.out.println(head.data);
head = head.next;
}
}
}
public static void main(String[] args){
Node root = new Node(1);
root.insert(2);
root.insert(3);
System.out.println("Reversed list :");
Node rev = root.reverse(root);
rev.display();
}
}
Output: 3->2->1
Time Complexity : O(N)
Space Complexity : O(1)
No comments:
Post a Comment