Given a Linked List. The task is to traverse the Linked List from middle to left-right order using recursion.
For Example:
If the given Linked List is: 2 -> 5 -> 8 -> 3 -> 7 -> 9 -> 12 -> NULL
The Middle to left-right order is : 3, 8, 7, 5, 9, 2, 12
Explanation: Middle of the given linked list is ‘3’ so, we start traversing from middle by printing 3 then left and right of 3, so we print 8, 7 then print left of 8 and right of 7, so we print 5, 9 then print left of 5 and right of 9, so we print 2, 12.
Note: If number of node are even in a Linked List then print left right only. For this linked list( contains even number of nodes ) 2 -> 5 -> 8 -> 7 -> 9 -> 12 -> NULL.
The output should be 8, 7, 5, 9, 2, 12.
Examples:
Input: 20 -> 15 -> 23 -> 13 -> 19 -> 32 -> 16 -> 41 -> 11 -> NULL
Output: 19, 13, 32, 23, 16, 15, 41, 20, 11.
Input: 12 -> 25 -> 51 -> 16 -> 9 -> 90 -> 7 -> 2 -> NULL
Output: 16, 9, 51, 90, 25, 7, 12, 2.
Approach:
First, calculate the size of the linked list:
- If size is odd:
-> Then go to the (n+1)/2 -th node using recursion. - If size is even:
-> Then go to the n/2 -th node using recursion. - Now print node data and return next node address, do this procedure unless function call stack empty.
Below is the implementation of the above approach:
C++
// A C++ program to demonstrate// the printing of Linked List middle// to left right order#include <bits/stdc++.h>using namespace std;// A linked list nodeclass Node {public: int data; Node* next;};// Given a reference (pointer to pointer)// to the head of a list and an int, appends// a new node at the endvoid append(Node** head_ref, int new_data){ // Allocate node Node* new_node = new Node(); // Used in step 5 Node* last = *head_ref; // Put in the data new_node->data = new_data; // This new node is going to be // the last node, so make next of // it as NULL new_node->next = NULL; // If the Linked List is empty, // then make the new node as head if (*head_ref == NULL) { *head_ref = new_node; return; } // Else traverse till the last node while (last->next != NULL) last = last->next; // Change the next of last node last->next = new_node; return;}// This function prints contents of// linked list starting from headvoid printList(Node* node){ while (node != NULL) { cout << " " << node->data; if (node->next != NULL) cout << "->"; node = node->next; }}// Function to get the size of linked listint getSize(Node* head){ if (head == NULL) return 0; return 1 + getSize(head->next);}// Utility function to print the Linked List// from middle to left right orderNode* printMiddleToLeftRightUtil(Node* head, int counter, int lSize){ // Base Condition // When size of list is odd if (counter == 1 && lSize % 2 != 0) { // Print node value cout << head->data; // Returns address of next node return head->next; } // Base Condition // When size of list is even else if (counter == 1) { // Print node value // and next node value cout << head->data; cout << " , " << head->next->data; // Returns address of next to next node return head->next->next; } else { // Recursive function call and // store return address Node* ptr = printMiddleToLeftRightUtil( head->next, counter - 1, lSize); // Print head data cout << " , " << head->data; // Print ptr data cout << " , " << ptr->data; // Returns address of next node return ptr->next; }}// Function to print Middle to// Left-right ordervoid printMiddleToLeftRight(Node* head){ // Function call to get the size // Of Linked List int listSize = getSize(head); int middle = 0; // Store middle when Linked // List size is odd if (listSize % 2 != 0) { middle = (listSize + 1) / 2; } // Store middle when Linked // List size is even else { middle = listSize / 2; } // Utility function call print // Linked List from Middle // to left right order cout << "Output : "; printMiddleToLeftRightUtil(head, middle, listSize);}// Driver codeint main(){ // Start with the empty list Node* head = NULL; // Insert 6. So linked list // becomes 6->NULL append(&head, 6); // Insert 6. So linked list // becomes 6->4->NULL append(&head, 4); append(&head, 8); append(&head, 7); append(&head, 9); append(&head, 11); append(&head, 2); // After inserting linked list // becomes 6->4->8->7->9->11->2->NULL cout << "Created Linked list is: "; // Function to display Linked List content printList(head); cout << endl; // Function call print Linked List from // Middle to left right order printMiddleToLeftRight(head); return 0;} |
Java
// A Java program to demonstrate// the printing of Linked List middle// to left right orderclass GFG{// A linked list nodestatic class Node{ int data; Node next;};// Given a reference (pointer to pointer)// to the head of a list and an int, appends// a new node at the endstatic Node append(Node head_ref, int new_data){ // Allocate node Node new_node = new Node(); // Used in step 5 Node last = head_ref; // Put in the data new_node.data = new_data; // This new node is going to be // the last node, so make next of // it as null new_node.next = null; // If the Linked List is empty, // then make the new node as head if (head_ref == null) { head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; return head_ref;}// This function prints contents of// linked list starting from headstatic void printList(Node node){ while (node != null) { System.out.print( " " + node.data); if (node.next != null) System.out.print("->"); node = node.next; }}// Function to get the size of linked liststatic int getSize(Node head){ if (head == null) return 0; return 1 + getSize(head.next);}// Utility function to print the Linked List// from middle to left right orderstatic Node printMiddleToLeftRightUtil(Node head, int counter, int lSize){ // Base Condition // When size of list is odd if (counter == 1 && lSize % 2 != 0) { // Print node value System.out.print( head.data); // Returns address of next node return head.next; } // Base Condition // When size of list is even else if (counter == 1) { // Print node value // and next node value System.out.print(head.data); System.out.print( " , " + head.next.data); // Returns address of next to next node return head.next.next; } else { // Recursive function call and // store return address Node ptr = printMiddleToLeftRightUtil(head.next, counter - 1, lSize); // Print head data System.out.print(" , " + head.data); // Print ptr data System.out.print(" , " + ptr.data); // Returns address of next node return ptr.next; }}// Function to print Middle to// Left-right orderstatic void printMiddleToLeftRight(Node head){ // Function call to get the size // Of Linked List int listSize = getSize(head); int middle = 0; // Store middle when Linked // List size is odd if (listSize % 2 != 0) { middle = (listSize + 1) / 2; } // Store middle when Linked // List size is even else { middle = listSize / 2; } // Utility function call print // Linked List from Middle // to left right order System.out.print("Output : "); printMiddleToLeftRightUtil(head, middle, listSize);}// Driver codepublic static void main(String args[]){ // Start with the empty list Node head = null; // Insert 6. So linked list // becomes 6.null head = append(head, 6); // Insert 6. So linked list // becomes 6.4.null head = append(head, 4); head = append(head, 8); head = append(head, 7); head = append(head, 9); head = append(head, 11); head = append(head, 2); // After inserting linked list // becomes 6.4.8.7.9.11.2.null System.out.print("Created Linked list is: "); // Function to display Linked List content printList(head); System.out.println(); // Function call print Linked List from // Middle to left right order printMiddleToLeftRight(head);}}// This code is contributed by Arnab Kundu |
Python3
# A Python3 program to demonstrate# the printing of Linked List middle# to left right order # A linked list nodeclass Node: def __init__(self): self.data = 0 self.next = None # Given a reference (pointer to pointer)# to the head of a list and an int, appends# a new node at the enddef append(head_ref, new_data): # Allocate node new_node = Node(); # Used in step 5 last = head_ref; # Put in the data new_node.data = new_data; # This new node is going to be # the last node, so make next of # it as None new_node.next = None; # If the Linked List is empty, # then make the new node as head if (head_ref == None): head_ref = new_node; return head_ref; # Else traverse till the last node while (last.next != None): last = last.next; # Change the next of last node last.next = new_node; return head_ref; # This function prints contents of# linked list starting from head def printList(node): while (node != None): print(' ' + str(node.data), end = '') if (node.next != None): print('->', end = '') node = node.next; # Function to get the size of linked listdef getSize(head): if (head == None): return 0; return 1 + getSize(head.next);# Utility function to print the Linked List# from middle to left right orderdef printMiddleToLeftRightUtil(head, counter, lSize): # Base Condition # When size of list is odd if (counter == 1 and lSize % 2 != 0): # Print node value print(head.data, end = '') # Returns address of next node return head.next; # Base Condition # When size of list is even elif (counter == 1): # Print node value # and next node value print(str(head.data) + ' , ' + str(head.next.data), end = '') # Returns address of next to next node return head.next.next; else: # Recursive function call and # store return address ptr = printMiddleToLeftRightUtil(head.next, counter - 1,lSize); # Print head data print(' , ' + str(head.data) + ' , ' + str(ptr.data), end = '') # Returns address of next node return ptr.next; # Function to print Middle to# Left-right orderdef printMiddleToLeftRight(head): # Function call to get the size # Of Linked List listSize = getSize(head); middle = 0; # Store middle when Linked # List size is odd if (listSize % 2 != 0): middle = (listSize + 1) // 2; # Store middle when Linked # List size is even else: middle = listSize // 2; # Utility function call print # Linked List from Middle # to left right order print('Output :', end = ' ') printMiddleToLeftRightUtil(head, middle, listSize); # Driver codeif __name__=='__main__': # Start with the empty list head = None; # Insert 6. So linked list # becomes 6.None head = append(head, 6); # Insert 6. So linked list # becomes 6.4.None head = append(head, 4); head = append(head, 8); head = append(head, 7); head = append(head, 9) head = append(head, 11); head = append(head, 2) # After inserting linked list # becomes 6.4.8.7.9.11.2.None print("Created Linked list is:", end = ' ') # Function to display Linked List content printList(head); print() # Function call print Linked List from # Middle to left right order printMiddleToLeftRight(head); # This code is contributed by rutvik_56 |
C#
// A C# program to demonstrate// the printing of Linked List middle// to left right orderusing System;public class GFG{ // A linked list nodepublic class Node{ public int data; public Node next;}; // Given a reference (pointer to pointer)// to the head of a list and an int, appends// a new node at the endstatic Node append(Node head_ref, int new_data){ // Allocate node Node new_node = new Node(); // Used in step 5 Node last = head_ref; // Put in the data new_node.data = new_data; // This new node is going to be // the last node, so make next of // it as null new_node.next = null; // If the Linked List is empty, // then make the new node as head if (head_ref == null) { head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; return head_ref;} // This function prints contents of// linked list starting from headstatic void printList(Node node){ while (node != null) { Console.Write( " " + node.data); if (node.next != null) Console.Write("->"); node = node.next; }} // Function to get the size of linked liststatic int getSize(Node head){ if (head == null) return 0; return 1 + getSize(head.next);} // Utility function to print the Linked List// from middle to left right orderstatic Node printMiddleToLeftRightUtil(Node head, int counter, int lSize){ // Base Condition // When size of list is odd if (counter == 1 && lSize % 2 != 0) { // Print node value Console.Write( head.data); // Returns address of next node return head.next; } // Base Condition // When size of list is even else if (counter == 1) { // Print node value // and next node value Console.Write(head.data); Console.Write( " , " + head.next.data); // Returns address of next to next node return head.next.next; } else { // Recursive function call and // store return address Node ptr = printMiddleToLeftRightUtil(head.next, counter - 1, lSize); // Print head data Console.Write(" , " + head.data); // Print ptr data Console.Write(" , " + ptr.data); // Returns address of next node return ptr.next; }} // Function to print Middle to// Left-right orderstatic void printMiddleToLeftRight(Node head){ // Function call to get the size // Of Linked List int listSize = getSize(head); int middle = 0; // Store middle when Linked // List size is odd if (listSize % 2 != 0) { middle = (listSize + 1) / 2; } // Store middle when Linked // List size is even else { middle = listSize / 2; } // Utility function call print // Linked List from Middle // to left right order Console.Write("Output : "); printMiddleToLeftRightUtil(head, middle, listSize);} // Driver codepublic static void Main(String []args){ // Start with the empty list Node head = null; // Insert 6. So linked list // becomes 6.null head = append(head, 6); // Insert 6. So linked list // becomes 6.4.null head = append(head, 4); head = append(head, 8); head = append(head, 7); head = append(head, 9); head = append(head, 11); head = append(head, 2); // After inserting linked list // becomes 6.4.8.7.9.11.2.null Console.Write("Created Linked list is: "); // Function to display Linked List content printList(head); Console.WriteLine(); // Function call print Linked List from // Middle to left right order printMiddleToLeftRight(head);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to demonstrate// the printing of Linked List middle// to left right order// Structure of a node of the linked listclass Node { constructor() { this.data = 0; this.next = null; }}// Given a reference (pointer to pointer)// to the head of a list and an int, appends// a new node at the endfunction append( head_ref, new_data){ // Allocate node var new_node = new Node(); // Used in step 5 var last = head_ref; // Put in the data new_node.data = new_data; // This new node is going to be // the last node, so make next of // it as null new_node.next = null; // If the Linked List is empty, // then make the new node as head if (head_ref == null) { head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; return head_ref;}// This function prints contents of// linked list starting from headfunction printList( node){ while (node != null) { document.write( " " + node.data); if (node.next != null) document.write("->"); node = node.next; }}// Function to get the size of linked listfunction getSize( head){ if (head == null) return 0; return 1 + getSize(head.next);}// Utility function to print the Linked List// from middle to left right orderfunction printMiddleToLeftRightUtil( head, counter, lSize){ // Base Condition // When size of list is odd if (counter == 1 && lSize % 2 != 0) { // Print node value document.write( head.data); // Returns address of next node return head.next; } // Base Condition // When size of list is even else if (counter == 1) { // Print node value // and next node value document.write(head.data); document.write( " , " + head.next.data); // Returns address of next to next node return head.next.next; } else { // Recursive function call and // store return address var ptr = printMiddleToLeftRightUtil(head.next, counter - 1, lSize); // Print head data document.write(" , " + head.data); // Print ptr data document.write(" , " + ptr.data); // Returns address of next node return ptr.next; }}// Function to print Middle to// Left-right orderfunction printMiddleToLeftRight( head){ // Function call to get the size // Of Linked List let listSize = getSize(head); let middle = 0; // Store middle when Linked // List size is odd if (listSize % 2 != 0) { middle = Math.floor((listSize + 1) / 2); } // Store middle when Linked // List size is even else { middle = Math.floor(listSize / 2); } // Utility function call print // Linked List from Middle // to left right order document.write("Output : "); printMiddleToLeftRightUtil(head, middle, listSize);}// Driver Code// Start with the empty listvar head = null;// Insert 6. So linked list// becomes 6.nullhead = append(head, 6);// Insert 6. So linked list// becomes 6.4.nullhead = append(head, 4);head = append(head, 8);head = append(head, 7);head = append(head, 9);head = append(head, 11);head = append(head, 2);// After inserting linked list// becomes 6.4.8.7.9.11.2.nulldocument.write("Created Linked list is: ");// Function to display Linked List contentprintList(head);document.write("</br>");// Function call print Linked List from// Middle to left right orderprintMiddleToLeftRight(head); </script> |
Output:
Created Linked list is: 6-> 4-> 8-> 7-> 9-> 11-> 2 Output : 7 , 8 , 9 , 4 , 11 , 6 , 2
Time complexity: O(N) where N is the size of the given linked list
Auxiliary space: O(N) for call stack
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
