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.
[pastacode lang=”java” manual=”public%20static%20Node%20reverseLinkedList(Node%20currentNode)%0A%09%7B%0A%09%09%2F%2F%20For%20first%20node%2C%20previousNode%20will%20be%20null%0A%09%09Node%20previousNode%3Dnull%3B%0A%09%09Node%20nextNode%3B%0A%09%09while(currentNode!%3Dnull)%0A%09%09%7B%0A%09%09%09nextNode%3DcurrentNode.next%3B%0A%09%09%09%2F%2F%20reversing%20the%20link%0A%09%09%09currentNode.next%3DpreviousNode%3B%0A%09%09%09%2F%2F%20moving%20currentNode%20and%20previousNode%20by%201%20node%0A%09%09%09previousNode%3DcurrentNode%3B%0A%09%09%09currentNode%3DnextNode%3B%0A%09%09%7D%0A%09%09return%20previousNode%3B%0A%09%7D” message=”” highlight=”” provider=”manual”/]
Sample Code in Java:
[pastacode lang=”java” manual=”public%20class%20LinkedList%7B%0A%20%0A%09private%20Node%20head%3B%0A%20%0A%09private%20static%20class%20Node%20%7B%0A%09%09private%20int%20value%3B%0A%09%09private%20Node%20next%3B%0A%20%0A%09%09Node(int%20value)%20%7B%0A%09%09%09this.value%20%3D%20value%3B%0A%20%0A%09%09%7D%0A%09%7D%0A%20%0A%09public%20void%20addToTheLast(Node%20node)%20%7B%0A%20%0A%09%09if%20(head%20%3D%3D%20null)%20%7B%0A%09%09%09head%20%3D%20node%3B%0A%09%09%7D%20else%20%7B%0A%09%09%09Node%20temp%20%3D%20head%3B%0A%09%09%09while%20(temp.next%20!%3D%20null)%0A%09%09%09%09temp%20%3D%20temp.next%3B%0A%20%0A%09%09%09temp.next%20%3D%20node%3B%0A%09%09%7D%0A%09%7D%0A%20%0A%20%0A%09public%20void%20printList(Node%20head)%20%7B%0A%09%09Node%20temp%20%3D%20head%3B%0A%09%09while%20(temp%20!%3D%20null)%20%7B%0A%09%09%09System.out.format(%22%25d%20%22%2C%20temp.value)%3B%0A%09%09%09temp%20%3D%20temp.next%3B%0A%09%09%7D%0A%09%09System.out.println()%3B%0A%09%7D%0A%20%0A%09%2F%2F%20Reverse%20linkedlist%20using%20this%20function%20%0A%09public%20static%20Node%20reverseLinkedList(Node%20currentNode)%0A%09%7B%0A%09%09%2F%2F%20For%20first%20node%2C%20previousNode%20will%20be%20null%0A%09%09Node%20previousNode%3Dnull%3B%0A%09%09Node%20nextNode%3B%0A%09%09while(currentNode!%3Dnull)%0A%09%09%7B%0A%09%09%09nextNode%3DcurrentNode.next%3B%0A%09%09%09%2F%2F%20reversing%20the%20link%0A%09%09%09currentNode.next%3DpreviousNode%3B%0A%09%09%09%2F%2F%20moving%20currentNode%20and%20previousNode%20by%201%20node%0A%09%09%09previousNode%3DcurrentNode%3B%0A%09%09%09currentNode%3DnextNode%3B%0A%09%09%7D%0A%09%09return%20previousNode%3B%0A%09%7D%0A%20%0A%09public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%09%09LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%09%09%2F%2F%20Creating%20a%20linked%20list%0A%09%09Node%20head%3Dnew%20Node(5)%3B%0A%09%09list.addToTheLast(head)%3B%0A%09%09list.addToTheLast(new%20Node(6))%3B%0A%09%09list.addToTheLast(new%20Node(7))%3B%0A%09%09list.addToTheLast(new%20Node(1))%3B%0A%09%09list.addToTheLast(new%20Node(2))%3B%0A%20%0A%09%09list.printList(head)%3B%0A%09%09%2F%2FReversing%20LinkedList%0A%09%09Node%20reverseHead%3DreverseLinkedList(head)%3B%0A%09%09System.out.println(%22After%20reversing%22)%3B%0A%09%09list.printList(reverseHead)%3B%0A%20%0A%09%7D%0A%20%0A%7D” message=”” highlight=”” provider=”manual”/]Output :
5 6 7 1 2
After reversing
2 1 7 6 5Recursive 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
