Recursive approach :- When we think of reversal of linked list by recursion, the very first thing comes in mind - reach at end of list and come back to starting point. Lets write the sample code and understand each steps involved from associated in-line comments.
/* Reverse a singly linked list using recursion */
static public Node reverseLinkedListUsingRecursion(Node head) {
/* Return null , if list is empty or head if head.next = null */
if (head == null || head.getNext() == null) {
return head;
} else {
/* Store next node of list */
Node nextNode = head.getNext();
/* For storing reference of last node of list */
Node retHead = reverseLinkedListUsingRecursion(nextNode);
/* Set next reference of the given node to null, breaking the chain */
head.setNext(null);
/* Add next reference in reverse order */
nextNode.setNext(head);
/* Return last node of the given list */
return retHead;
}
}
Iterative approach :- Writing iterative code is memory efficient and easy to understand.Below is the sample code for the same.Go through the in-line comments associated with each step.
/* Reverse a singly linked list */
static public Node reverseLinkedListIterative(Node head) {
/* Return null , if list is empty or head if head.next Is null */
if (head == null || head.getNext() == null) {
return head;
} else {
Node previous = null;
Node current = head;
Node curNext;
/* Iterate linked list and reverse the next reference for each node */
while (current != null) {
curNext = current.getNext();// Store next node for iteration
current.setNext(previous); // set current next as previous
/* store current in previous, for next iteration */
previous = current;
current = curNext;
}
/*
* Once we complete the list iteration, previous refers to last
* node, so assign that to head
*/
head = previous;
}
return head;
}
Here is the complete sample program for the reversal of linked list using recursive and Iterative approach:-
package com.devinline.linkedlist;
public class ReverseSinglyLinkedlist {
static Node head = null;
/* Reverse a singly linked list using recursion */
static public Node reverseLinkedListUsingRecursion(Node head) {
/* Return null , if list is empty or head if head.next = null */
if (head == null || head.getNext() == null) {
return head;
} else {
/* Store next node of list */
Node nextNode = head.getNext();
/* For storing reference of last node of list */
Node retHead = reverseLinkedListUsingRecursion(nextNode);
/* Set next reference of the given node to null, breaking the chain */
head.setNext(null);
/* Add next reference in reverse order */
nextNode.setNext(head);
/* Return last node of the given list */
return retHead;
}
}
/* Reverse a singly linked list */
static public Node reverseLinkedListIterative(Node head) {
/* Return null , if list is empty or head if head.next Is null */
if (head == null || head.getNext() == null) {
return head;
} else {
Node previous = null;
Node current = head;
Node curNext;
/* Iterate linked list and reverse the next reference for each node */
while (current != null) {
curNext = current.getNext();// Store next node for iteration
current.setNext(previous); // set current next as previous
/* store current in previous, for next iteration */
previous = current;
current = curNext;
}
/*
* Once we complete the list iteration, previous refers to last
* node, so assign that to head
*/
head = previous;
}
return head;
}
private static Node createNewNode(int data) {
/*Inner class Object creation*/
return new ReverseSinglyLinkedlist().new Node(data);
}
/* Add New node at start of linked list */
private static void insertFirst(int data) {
Node newNode = createNewNode(data);
if (head == null) {
head = newNode;
} else {
newNode.setNext(head);
head = newNode;
}
}
/* Display data of nodes/iterate linked list */
private static void iterateLinedList(Node head) {
Node current = head;
if (head != null) {
System.out.print("[");
while (current != null) {
System.out.print(current.getData() + " ");
current = current.getNext();
}
System.out.print(" ]\n");
} else {
System.out.println("Linked list is empty.");
}
}
class Node {
private int data;
private Node next; // reference(handler) for next Node.
public Node(int data) {
this.data = data;
this.next = null;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getData() {
return data;
}
}
public static void main(String[] args) {
/* Setup a linked list */
insertFirst(142);
insertFirst(135);
insertFirst(141);
insertFirst(141);
insertFirst(145);
insertFirst(148);
insertFirst(145);
/* Original linked list display */
System.out.println("Original linked list ");
iterateLinedList(head);
/* Reverse a singly linked list using recursion and display the same */
Node newhead1 = ReverseSinglyLinkedlist
.reverseLinkedListUsingRecursion(head);
System.out.println("Reversed linked list(Recursive approach) ");
iterateLinedList(newhead1);
/* Reverse a singly linked list using iterative and display the same */
Node newhead2 = ReverseSinglyLinkedlist
.reverseLinkedListIterative(newhead1);
System.out.println("Reversed linked list(Iterative appraoch) ");
iterateLinedList(newhead2);
}
}
Original linked list
[145 148 145 141 141 135 142 ]
Reversed linked list(Recursive approach)
[142 135 141 141 145 148 145 ]
Reversed linked list(Iterative appraoch)
[145 148 145 141 141 135 142 ]
=================================
0 comments:
Post a Comment