Write a Java program to Reverse Linked List using Stack
The code demonstrates how to reverse a linked list using a stack in Java. Let's go through the code step by step:
- The code begins with the import statement import java.util.Stack; , which imports the Stack class from the java.util package.
- The ReverseLinkedList class is defined, serving as the entry point of the program.
- In the main method, a linked list is created with five nodes. Each node is assigned a value using the ListNode class. The next pointers are set to create a linked list structure.
- The reverseList method is called, passing the head of the linked list as an argument. This method reverses the linked list and returns the new head of the reversed list.
- The reverseList method takes the head of the original linked list as a parameter.
- If the linked list is empty or has only one node, it is already reversed, so the method returns the head as it is.
- A Stack object named stack is created to store the nodes of the linked list.
- The linked list is traversed, and each node is pushed onto the stack using the push method.
- The first node of the reversed list is set as the top element of the stack, which is obtained using the pop method. This node will become the new head of the reversed list.
- A pointer current is created and initialized with the new head node.
- In a loop, nodes are popped from the stack using the pop method and assigned as the next node to the current pointer. This effectively reverses the pointers in the linked list.
- Finally, the next pointer of the last node in the reversed list is set to null to mark the end of the list.
- The method returns the new head of the reversed list.
- The printLinkedList method takes the head of a linked list as a parameter and prints the values of all nodes in the list.
- In the printLinkedList method, a pointer current is initialized with the head of the list.
- In a loop, the values of the nodes are printed using the System.out.print statement, and the current pointer is updated to the next node until the end of the list is reached.
Source Code
import java.util.Stack;
public class ReverseLinkedList
{
public static void main(String[] args)
{
ListNode head = new ListNode(10);
head.next = new ListNode(20);
head.next.next = new ListNode(30);
head.next.next.next = new ListNode(40);
head.next.next.next.next = new ListNode(50);
ListNode reversed = reverseList(head);
printLinkedList(reversed);
}
public static ListNode reverseList(ListNode head)
{
if (head == null || head.next == null)
{
return head;
}
Stack<ListNode> stack = new Stack<>();
while (head != null)
{
stack.push(head);
head = head.next;
}
ListNode newHead = stack.pop();
ListNode current = newHead;
while (!stack.isEmpty())
{
current.next = stack.pop();
current = current.next;
}
current.next = null;
return newHead;
}
public static void printLinkedList(ListNode head)
{
ListNode current = head;
while (current != null)
{
System.out.print(current.val + " ");
current = current.next;
}
}
}
class ListNode
{
int val;
ListNode next;
ListNode(int val)
{
this.val = val;
}
}
Output
50 40 30 20 10