Hi! In this Data structures tutorial we are going to find solution of trending interview question how to reverse Singly List in java(keeping in mind time complexity should be O(n).
It may sound bit trickier to reverse Singly List, but it can be easily achieved by using 3pointers (previousNode, currentNode and nextNode)
Read : What is Singly LinkedList in java with example, how to implement your own Singly LinkedList in java.
What is Complexity of reversing Singly Linked List in java?
Complexity of reversing Singly SinglyList is O(n) in java.
Important methods used for reversing Singly Linked List in java >
>reverseLinkedList()
Logic explanation of reversing Singly Linked List in java with diagram >
Initially we will keep 3 pointers:
previousNode pointing to null.
currentNode and nextNode pointing to first.
STEP1:
execute below while loop.
while(nextNode!=null){
nextNode=nextNode.next; //make nextNode point to next node.
currentNode.next=previousNode; //make current node's next point to previous node.
previousNode=currentNode; //make previousNode point to currentNode.
currentNode=nextNode; //make currentNode point to nextNode.
}
STEP2:
execute while loop again.
STEP3:
execute while loop again.
STEP4:
execute while loop again.
STEP5:
Execute below statement.
first=previousNode; //which will make first point to previous node(i.e. last node).
Now we are reversed our LinkedList successfully. All the nodes are pointing to previous nodes.
Full Program/example/SourceCode for reversing Singly LinkedList>
/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.
/**
* Constructor
*/
public Node(int data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
/**
* Singly LinkedList class
*/
class LinkedList {
private Node first; // ref to first link on list
/**
* Singly LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* REVERSE linkedList.
*/
public void reverseLinkedList() {
//Using 3 pointers for reversing LinkedList.
Node previousNode=null;
Node currentNode=first;
Node nextNode=first;
while(nextNode!=null){
nextNode=nextNode.next; //make nextNode point to next node.
currentNode.next=previousNode; //make current node's next point to previous node.
previousNode=currentNode; //make previousNode point to currentNode.
currentNode=nextNode; //make currentNode point to nextNode.
}
//by this stage of program all the nodes are pointing to previous nodes(which has helped us generating reverse of LinkedList.)
first=previousNode; //now make first point to previous node(i.e. last node).
System.out.println("LinkedList has been reversed successfully.");
}
/**
* Insert New Node at first position
*/
public void insertFirst(int data) {
Node newNode = new Node(data); //Creation of New Node.
newNode.next = first; //newLink ---> old first
first = newNode; //first ---> newNode
}
/**
* Display Singly LinkedList
*/
public void displayLinkedList() {
System.out.print("Displaying LinkedList [first--->last]: ");
Node tempDisplay = first; // start at the beginning of linkedList
while (tempDisplay != null){ // Executes until we don't find end of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println();
}
}
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
/**
* SinglyLinkedListReverseExample - Main class - To test LinkedList.
*/
public class SinglyLinkedListReverseExample {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insertFirst(4);
linkedList.insertFirst(3);
linkedList.insertFirst(2);
linkedList.insertFirst(1);
linkedList.displayLinkedList();
linkedList.reverseLinkedList(); //REVERSE LinkedList
linkedList.displayLinkedList();
}
}
/*OUTPUT
Displaying LinkedList [first--->last]: 1 2 3 4
LinkedList has been reversed successfully.
Displaying LinkedList [first--->last]: 4 3 2 1
*/
|
So, in the above java program we wrote logic to reverse Singly linkedlist in java.
Complexity of reversing SinglyList in java >
Complexity of reversing SinglyList is O(n), because we got to iterate over each and every node to reverse the Singly LinkedList in java.
So, in this Data structures tutorial we found solution to trending interview question how to reverse Singly List in java(keeping in mind time complexity should be O(n).
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>
1) Stacks, Queues in Data Structures in java
2) Single LinkedList implementations in Data Structures in java:-
>
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
3) Doubly LinkedList implementations in Data Structures in java:-
4)Implement Stack, Queue using LinkedList
5) Some of the tricky and interesting Single LinkedList implementations in Data Structures in java
6) Binary tree tutorial in java >