Wednesday, 4 September 2013

Reverse a linked list

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)

No comments:

Post a Comment