Topics covered
1. Recursive implementation 2. Non-recursive implementation
3. Complete sample program
Problem Statement :- For a given a linked list and block size N as input, reverse N blocks of nodes so that linked list internal structure is maintained. Solve using recursive and non-recursive approach.
Sample Input and Output:- Inputs: 12 --> 18 --> 172 --> 62 --> 632 --> 192 --> 34 , block size N = 3 Output: 172 --> 18 --> 12 --> 192 --> 632 --> 62 --> 34 Inputs: 12-->18-->172-->62-->632-->192-->2-->61-->82-->72-->32, block size N = 4 Output: 62-->172-->18-->12-->61-->2-->192-->632-->32-->72-->82
Recursive implementation - reverse a linked list in block of size N
Algorithm:-1 Iterate over input list and find end of blocks (move up to block size of N) and while traversing loop keep track of previous and next node. Lets say, Node references "nextNode" and "previous" keeps track of next node and previous node of input list.
2. Reverse block of nodes and append it with previous node. Refer how to reverse a linked list in Java?. In below sample code we have used recursive version for linked list reversal.
3. Recursively call this method for next set of blocks and link the two sub-lists (head.next = reverseLinkedListInBlocksRecursive(nextNode, blockSize) )
4. Finally, once we reaches at end and recursive call is returned to caller and return previous as new head of the list (previous is storing first node of modified sub-list(of size N)).
5. Check for special cases - for empty list and one node list.
/* * Recursive approach- reverse the linked list in group (block of size N) * and returns new head node. */ private Node reverseLinkedListInBlocksRecursive(Node head, int blockSize) { Node current = head; Node nextNode = null; Node previous = null; int size = 0; /* * Check for empty and one node list */ if (current == null || current.next == null) return current; /* Iterate and find end of blocks */ while (current != null && size < blockSize) { nextNode = current.next; previous = current; current = nextNode; size++; } /* split sublist from main linked list */ previous.next = null; /* Reverse block of nodes only if size is blockSize */ if (size == blockSize) { previous = reverseLinkedListUsingRecursion(head); } /* * Recursive call for next blocks of nodes and make rest of the list as next of * first node */ if (nextNode != null) { head.next = reverseLinkedListInBlocksRecursive(nextNode, blockSize); } /* Return previous as new head of the input list */ if (size == blockSize) return previous; else return head; }
Iterative implementation - reverse a linked list in block of size N
Algorithm:-1. Do check for empty and single node list, if true return node to caller.
2. Traverse linked list maintaining current and previous node of while list along with of single block, current,previous and blockPrevious is used for input list and blockFirst and blockPrevious associated closely with each blocks(On close scrutiny may be some of variables may be minimized.)
3. Find the end of block and reverse sub-list(blocks of size N) and append with head or previous(appended with head first time and for other iteration appended with previous). Here we have used iterative version of linked list reversal.
4. Repeat step 2 and 3 , until whole list is traversed.
5. Do check for whether a single node is left, if true append with previous.
/*
* Iterative approach- reverse the linked list in group (block of size N)
* and returns new head node.
*/
private Node reverseLinkedListInBlocksIterative(Node head, int blockSize) {
Node current = head;
Node nextNode = null;
Node blockPrevious = null;
Node blockFirst = null;
Node previous = null;
/* Check for empty and one node list */
if (current == null || current.next == null)
return current;
/* Loop rest of the list and reverse blocks of nodes */
while (current != null && current.next != null) {
int size = 1;
blockFirst = current;
while (current != null && size <= blockSize) {
nextNode = current.next;
blockPrevious = current;
current = current.next;
size++;
}
blockPrevious.next = null;
/* Reverse block of nodes only if size is blockSize */
if (size == blockSize + 1 && previous == null) {
previous = head;
head = reverseLinkedListIterative(head);
} else {
Node temp = reverseLinkedListIterative(blockFirst);
previous.next = temp;
previous = blockFirst;
}
current = nextNode;
}
/* Check for isolated blocks */
if (current != null) {
previous.next = current;
}
/* Return modified head of the list */
return head;
}
Complete sample program- reverse a linked list in block of size N(Iterative and Recursive)
Below is complete sample program for reversing a linked list in blocks(of size N) in recursive and iterative way :-package com.devinline.linkedlist;
public class ReverseLinkedListElementsInBlocks {
/*
* Recursive approach- reverse the linked list in group (block of size N)
* and returns new head node.
*/
private Node reverseLinkedListInBlocksRecursive(Node head, int blockSize) {
Node current = head;
Node nextNode = null;
Node previous = null;
int size = 0;
/*
* Check for empty and one node list
*/
if (current == null || current.next == null)
return current;
/* Iterate and find end of blocks */
while (current != null && size < blockSize) {
nextNode = current.next;
previous = current;
current = nextNode;
size++;
}
/* split sublist from main linked list */
previous.next = null;
/* Reverse block of nodes only if size is 3 */
if (size == blockSize) {
previous = reverseLinkedListUsingRecursion(head);
}
/*
* Recursive call for next blocks and make rest of the list as next of
* first node
*/
if (nextNode != null) {
head.next = reverseLinkedListInBlocksRecursive(nextNode, blockSize);
}
/* Return previous as new head of the input list */
if (size == blockSize)
return previous;
else
return head;
}
/*
* Iterative approach- reverse the linked list in group (block of size N)
* and returns new head node.
*/
private Node reverseLinkedListInBlocksIterative(Node head, int blockSize) {
Node current = head;
Node nextNode = null;
Node blockPrevious = null;
Node blockFirst = null;
Node previous = null;
/* Check for empty and one node list */
if (current == null || current.next == null)
return current;
/* Loop rest of the list and reverse blocks of nodes */
while (current != null && current.next != null) {
int size = 1;
blockFirst = current;
while (current != null && size <= blockSize) {
nextNode = current.next;
blockPrevious = current;
current = current.next;
size++;
}
blockPrevious.next = null;
/* Reverse block of nodes only if size is 3 */
if (size == blockSize + 1 && previous == null) {
previous = head;
head = reverseLinkedListIterative(head);
// displayLinkedList(head);
} else {
Node temp = reverseLinkedListIterative(blockFirst);
previous.next = temp;
previous = blockFirst;
}
current = nextNode;
}
/* Check for isolated blocks */
if (current != null) {
previous.next = current;
}
/* Return modified head of the list */
return head;
}
/* Reverse a singly linked list using recursion */
public Node reverseLinkedListUsingRecursion(Node head) {
/* Return null , if list is empty or head if head.next = null */
if (head == null || head.next == null) {
return head;
} else {
/* Store next node of list */
Node nextNode = head.next;
/* 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.next = null;
/* Add next reference in reverse order */
nextNode.next = head;
/* Return last node of the given list */
return retHead;
}
}
/* Reverse a singly linked list */
public Node reverseLinkedListIterative(Node head) {
/* Return null , if list is empty or head if head.next Is null */
if (head == null || head.next == 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.next;// Store next node for iteration
current.next = 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;
}
class Node {
public int data;
public Node next; // reference(handler) for next Node.
public Node(int data) {
this.data = data;
this.next = null;
}
}
/* Display data of nodes/iterate linked list */
private static void displayLinkedList(Node head) {
Node current = head;
if (head != null) {
System.out.print("[ ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.print(" ]");
} else {
System.out.println("Linked list is empty.");
}
}
public static void main(String[] args) {
ReverseLinkedListElementsInBlocks rpll = new ReverseLinkedListElementsInBlocks();
Node modifiedHead = null;
Node node1 = rpll.new Node(12);
Node node2 = rpll.new Node(18);
Node node3 = rpll.new Node(172);
Node node4 = rpll.new Node(62);
Node node5 = rpll.new Node(632);
Node node6 = rpll.new Node(192);
Node node7 = rpll.new Node(13);
Node node8 = rpll.new Node(19);
Node node9 = rpll.new Node(15);
Node node10 = rpll.new Node(67);
Node head = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next= node6;
node6.next = node7;
node7.next = node8;
node8.next = node9;
node9.next = node10;
System.out.print("Original list is :");
displayLinkedList(head);
System.out.print("\nModified linked list is "
+ "(Using recursive Implementation) with block size is 3\n");
modifiedHead = rpll.reverseLinkedListInBlocksRecursive(head, 3);
displayLinkedList(modifiedHead);
System.out.print("\n\nOriginal list is :");
displayLinkedList(modifiedHead);
System.out.print("\nModified linked list is "
+ "(Using Iterative Implementation:) block size is 2\n");
modifiedHead = rpll.reverseLinkedListInBlocksIterative(modifiedHead, 2);
displayLinkedList(modifiedHead);
}
}
Original list is :[ 12 18 172 62 632 192 13 19 15 67 ]
Modified linked list is (Using recursive Implementation) with block size is 3
[ 172 18 12 192 632 62 15 19 13 67 ]
Original list is :[ 172 18 12 192 632 62 15 19 13 67 ]
Modified linked list is (Using Iterative Implementation:) block size is 2
[ 18 172 192 12 62 632 19 15 67 13 ]
======================================