How to reverse a linked list in Java

 Reversal of linked list is one of those questions which is asked in technical interview . It is one of the most important question of linked list . 

Lets take few examples .

Input : 4  -> 2-> 1 -> 5 -> 3 -> 9-> NULL
Output : 9 -> 3 -> 5 -> 1 -> 2 -> 4 -> NULL
Explanation : If you reverse this list 9 will come first then 3, 5, 1, 2 and 4

Input : 8 -> NULL
Output : 8 -> NULL
Explanation : 8 is the only element in the linked list .

Input : NULL
Output : NULL
Explanation : Since there is no element in the linked list so it will remain empty.

Java Code :

class Node{

int data;

Node next;

Node(int data){

this.data=data;

}

}

class HindiCodingCommunity{

public static Node reverselist(Node head)

{

Node curr = head;

Node prev = null;

while(curr != null)

{

Node next = curr.next;

curr.next = prev;

prev = curr;

curr = next;

}

return prev;

}

public static void print(Node head)

{

Node h = reverselist(head);

Node curr = h;

while(curr!=null)

{

System.out.println(curr.data+ " ");

curr = curr.next;

}

}

public static void main(String args[])

{

Node head= new Node(10);

head.next= new Node(20);

head.next.next= new Node(30);

head.next.next.next= new Node(40);

print(head);

}

}

Output : 40 30 20 10

Time Complexity : O(n)

Space Complexity : O(1)