There are multiple ways of solving this problem :
1. Using Recursion in the O(n) time & O(n) space complexity:
/*** @author sachin**/
2. Using Iteration in time O(n) & space O(1) complexity :
This approach follows takes 3 Nodes current[head node] , next and previous , head node is looped to move forward and prev node follows it as below :
Before iteration :
head --> 1 --> 2 --> 3 --> 4 --> 5--> null
Node current = head;
Node next = null;
Node prev = null;
//iterate the head node to the end or till the null is found
while(current!=null){
next = current.next; //get the next node N
current.next=prev; //next node N assigned the value of prev node
prev = current; //prev node is assigned to current node
current = next; // current node is assigned to next node
}
head = prev; //head is assigned to prev node which has the node detail in reverse order
After iteration :
null <--1 <-- 2 <-- 3 <-- 4 <-- 5 <--- head
/**
* @author sachin
*
*/
public class LinkedListDemo {
static Node head;
static class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
next = null;
}
}
static Node reverse(Node head){
Node current = head;
Node next = null;
Node prev = null;
while(current!=null){
next = current.next;
current.next=prev;
prev = current;
current = next;
}
head = prev;
return head;
}
static void printList(Node head){
while(head!=null){
System.out.println(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
LinkedListDemo.head = new Node(25);
LinkedListDemo.head.next = new Node(35);
LinkedListDemo.head.next.next = new Node(14);
LinkedListDemo.head.next.next.next = new Node(12);
System.out.println("Original Linked list is :");
LinkedListDemo.printList(head);
System.out.println("Reversed linked list : ");
head = LinkedListDemo.reverse(head); //getting the head node after reversal
LinkedListDemo.printList(head);
}
}
Output :
Original Linked list is :
25
35
14
12
Reversed linked list :
12
14
35
25
Enjoy the coding !!!
