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!
No need to apologize, everyone starts somewhere. Linked lists can be reversed by changing the next to a previous node using iterative or recursive methods. Below you can find both methods:
**Iterative Method:**
```java
public Node reverseIteratively(Node node) {
Node previous = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next; // store the next node
current.next = previous; // reverse the link
previous = current; // move the step ahead for the next iteration
current = next;
}
node = previous;
return node;
}
```
Here `Node` is the structure of a single node, which might look like this:
```java
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
```
**Recursive Method:**
```java
public Node reverseRecursively(Node node) {
if (node == null || node.next == null) {
return node;
}
Node remaining = reverseRecursively(node.next);
node.next.next = node;
node.next = null;
return remaining;
}
```
In the recursive method, we recursively call the function for `node.next` until we reach the end of the list. Then, we change the link from `next` node to `current` node for each pair of nodes and continue this until all pairs are linked in reverse.
Remember you need to set both `node.next.next` and `node.next`. The former is to change the link direction, the latter is to avoid a cycle.
Hope this helps! Let me know if you need further information. Understanding linked lists and their manipulation is an important step in improving your knowledge of data structures and algorithms in Java.
