WikiGalaxy
Reversing Singly Linked List Structure
Understanding the Reversal Process:
Reversing a singly linked list involves changing the direction of the pointers such that the last node becomes the first node and vice versa.
Step-by-Step Diagram:
Step 1: Initial Linked List
[Head] -> [Data | Next] -> [Data | Next] -> [Data | Null]
Step 2: Start Reversing
[Head] <- [Data] <- [Data] <- [Data | Null]
Step 3: Reversed Linked List
[Null | Data] <- [Data] <- [Data] <- [Head]
Reversal Algorithm:
public class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
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;
}
}
Explanation of Code:
The algorithm initializes three pointers: prev, current, and next. It iteratively reverses the direction of each node's pointer until the entire list is reversed.
Console Output:
Reversed List: [3, 2, 1]
Example 1: Reversing an Empty List
Initial State:
An empty linked list has no nodes. Therefore, reversing it results in another empty list.
Step-by-Step Diagram:
Step 1: Initial Linked List
[Null]
Step 2: Attempt to Reverse
[Null]
Step 3: Reversed Linked List
[Null]
Conclusion:
Reversing an empty list does not change its structure.
Example 2: Reversing a Single-Node List
Initial State:
A list with a single node remains unchanged after reversal.
Step-by-Step Diagram:
Step 1: Initial Linked List
[Head] -> [Data | Null]
Step 2: Attempt to Reverse
[Head] -> [Data | Null]
Step 3: Reversed Linked List
[Head] -> [Data | Null]
Conclusion:
Reversing a single-node list results in the same list.
Example 3: Reversing a Two-Node List
Initial State:
A list with two nodes will have the pointers reversed between them.
Step-by-Step Diagram:
Step 1: Initial Linked List
[Head] -> [Data1 | Next] -> [Data2 | Null]
Step 2: Reverse Pointers
[Null | Data2] <- [Data1 | Head]
Step 3: Reversed Linked List
[Head] -> [Data2 | Next] -> [Data1 | Null]
Conclusion:
Reversing a two-node list swaps their positions.
Example 4: Reversing a Three-Node List
Initial State:
Reversing a list with three nodes involves multiple pointer adjustments.
Step-by-Step Diagram:
Step 1: Initial Linked List
[Head] -> [Data1 | Next] -> [Data2 | Next] -> [Data3 | Null]
Step 2: Reverse Pointers
[Null | Data3] <- [Data2] <- [Data1 | Head]
Step 3: Reversed Linked List
[Head] -> [Data3 | Next] -> [Data2 | Next] -> [Data1 | Null]
Conclusion:
Reversing a three-node list rearranges all node connections.
Example 5: Reversing a List with Multiple Nodes
Initial State:
For a list with multiple nodes, the reversal process is repeated for each pair of nodes.
Step-by-Step Diagram:
Step 1: Initial Linked List
[Head] -> [Data1 | Next] -> [Data2 | Next] -> ... -> [DataN | Null]
Step 2: Reverse Pointers Iteratively
[Null | DataN] <- ... <- [Data2] <- [Data1 | Head]
Step 3: Reversed Linked List
[Head] -> [DataN | Next] -> ... -> [Data2 | Next] -> [Data1 | Null]
Conclusion:
Reversing a list with multiple nodes involves iteratively changing the direction of each node's pointer.
