To reverse a linked list, we need to change the direction of the pointers of each node. We can achieve this by traversing the list and updating the next
pointer of each node to point to its previous node. We also need to keep track of the previous, current, and next nodes while traversing.
Here's a simple algorithm to reverse a singly linked list:
- Initialize three pointers:
prev
,current
, andnext
. Setprev
andnext
tonull
, andcurrent
to thehead
of the list. - Iterate through the list while the
current
pointer is notnull
:- Set
next
to thenext
node ofcurrent
. - Change the
next
pointer ofcurrent
to point toprev
. - Update
prev
tocurrent
. - Update
current
tonext
.
- Set
- After the iteration, update the
head
of the list to point to theprev
node, which is now the new first node of the reversed list.
Here's an example of a Java code snippet that reverses a singly linked list:
TEXT/X-JAVA
1class Node {
2 int data;
3 Node next;
4
5 public Node(int data) {
6 this.data = data;
7 this.next = null;
8 }
9}
10
11class LinkedList {
12 Node head;
13
14 // Reverse the linked list
15 void reverse() {
16 Node prev = null;
17 Node current = head;
18 Node next = null;
19
20 while (current != null) {
21 next = current.next;
22 current.next = prev;
23 prev = current;
24 current = next;
25 }
26 head = prev;
27 }
28}
xxxxxxxxxx
16
class Main {
public static void main(String[] args) {
// replace with your Java logic here
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment