Java Program to reverse a Linked List ?

  • A Linked list contains two things data and the address of the node each node is linked to the next node.
  • There can be two solution to reverse a linked list in java.

Iterative

  • Here we have three nodes i.e previousNode, currentNode and nextNode
  • When currentNode is starting node, then previousNode will be null
  • Assign currentNode.next to previousNode to reverse the link.
  • In each iteration move currentNode and previousNode by 1 node.
data- linked-list
public static Node reverseLinkedList(Node currentNode)
	{
		// For first node, previousNode will be null
		Node previousNode=null;
		Node nextNode;
		while(currentNode!=null)
		{
			nextNode=currentNode.next;
			// reversing the link
			currentNode.next=previousNode;
			// moving currentNode and previousNode by 1 node
			previousNode=currentNode;
			currentNode=nextNode;
		}
		return previousNode;
	}

Sample Code in Java:

public class LinkedList{
 
	private Node head;
 
	private static class Node {
		private int value;
		private Node next;
 
		Node(int value) {
			this.value = value;
 
		}
	}
 
	public void addToTheLast(Node node) {
 
		if (head == null) {
			head = node;
		} else {
			Node temp = head;
			while (temp.next != null)
				temp = temp.next;
 
			temp.next = node;
		}
	}
 
 
	public void printList(Node head) {
		Node temp = head;
		while (temp != null) {
			System.out.format("%d ", temp.value);
			temp = temp.next;
		}
		System.out.println();
	}
 
	// Reverse linkedlist using this function 
	public static Node reverseLinkedList(Node currentNode)
	{
		// For first node, previousNode will be null
		Node previousNode=null;
		Node nextNode;
		while(currentNode!=null)
		{
			nextNode=currentNode.next;
			// reversing the link
			currentNode.next=previousNode;
			// moving currentNode and previousNode by 1 node
			previousNode=currentNode;
			currentNode=nextNode;
		}
		return previousNode;
	}
 
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		// Creating a linked list
		Node head=new Node(5);
		list.addToTheLast(head);
		list.addToTheLast(new Node(6));
		list.addToTheLast(new Node(7));
		list.addToTheLast(new Node(1));
		list.addToTheLast(new Node(2));
 
		list.printList(head);
		//Reversing LinkedList
		Node reverseHead=reverseLinkedList(head);
		System.out.println("After reversing");
		list.printList(reverseHead);
 
	}
 
}

Output :

5 6 7 1 2 
After reversing
2 1 7 6 5

Recursive Method:

  • Divide the list in two parts – first node and rest of the linked list.
  • Call reverse for the rest of the linked list.
  • Link rest to first.
  • Fix head pointer
data- linked-list

Categorized in:

Java

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,