Given a singly linked list , write a code to reverse a linked list. In this tutorial, you are going to learn how to reverse a linked list in java using iterative approach.
For example –
Input linked list.
15 -> 9 -> 8 -> 5 -> NULL
When we reverse this linked list then the output is given below.
5 -> 8 -> 9 -> 15 -> NULL
In input linked list, head points to a node whose value is 15 but when it’s reversed the head points to a node whose value is 5.
We can reverse a linked list by using either iterative or recursive approach. In this tutorial, I am going to focus mainly on iterative approach to reverse a singly linked list.
Programming Video Tutorials
Recursion Vs Iteration
Reverse a Linked List in Java
To reverse a linked list in-place, what we have to do is to reverse the pointers such that the next element points to the previous node.
Here are the following steps –
i) Declare three variables previous, curr and temp.
ii) Traverse a linked list while curr is not null. Then Save the next Node of the current element in the temp pointer.
iii) Set the next of the current Node to the previous. Then shift previous to current and current element to temp (which is next).
Remove duplicates from a sorted linked list
I have explained this approach using video tutorial, the link of that video tutorial is present at the end of this post.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
Reverse a linked list java code
*/
//Node Class
public class Node {
int data ;
Node next ;
public Node ( int data ) {
this . data = data ;
this . next = null ;
}
}
//Actual Implementation
public class ReverseLinkedList {
//Insert node at head
public Node insertAtHead ( Node head , int data ) {
if ( head == null ) {
head = new Node ( data ) ;
} else {
// Create a new node
Node temp = new Node ( data ) ;
// New node points to head
temp . next = head ;
// Head points to a new node
head = temp ;
}
return head ;
}
public Node reverseLinkedList ( Node head ) {
Node previous = null ;
Node curr = head ;
Node temp = null ;
while ( curr != null ) {
temp = curr . next ;
curr . next = previous ;
previous = curr ;
curr = temp ;
}
return previous ;
}
public void print ( Node head ) {
Node temp = head ;
while ( temp != null ) {
System . out . print ( temp . data + " -> " ) ;
temp = temp . next ;
}
System . out . print ( "null" ) ;
System . out . println ( " " ) ;
}
public static void main ( String [ ] args ) {
Node head = null ;
ReverseLinkedList ll = new ReverseLinkedList ( ) ;
head = ll . insertAtHead ( head , 5 ) ;
head = ll . insertAtHead ( head , 8 ) ;
head = ll . insertAtHead ( head , 9 ) ;
head = ll . insertAtHead ( head , 15 ) ;
System . out . println ( " Linked List " ) ;
ll . print ( head ) ;
Node reverse = ll . reverseLinkedList ( head ) ;
System . out . println ( " Reverse Linked List " ) ;
ll . print ( reverse ) ;
}
}
In this video tutorial, I have explained how we can reverse a linked list using iterative approach.
