RE: How to reverse a linked list in Java?
Here is a simple method to reverse a linked list in Java. I will take a singly linked list as an example and use the most common method which is iterative:
```java
public class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
public void add(int data) {
Node toAdd = new Node(data);
if (head == null) {
head = toAdd;
return;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = toAdd;
}
public void reverse() {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Add elements to the list
list.add(10);
list.add(20);
list.add(30);
list.add(40);
// Print current list
list.printList();
list.reverse();
// Print reversed list
list.printList();
}
}
```
It can be broken down into the following steps:
1. Create a current node set to head.
2. Loop through your linked list.
3. In each iteration, set the `next` of the current node to a `previous` node.
4. Move the 'previous' and 'current' one step forward.
5. Last or tail node will become the head because 'current' can point to 'null' only if list is fully traversed.
This method only traverses the list once and uses constant memory - O(1) space complexity.
Hope that helps!
