Java Program to reverse a Linked List ?

  • 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:

Tagged in:

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