Dada una lista enlazada. La tarea es recorrer la Lista Enlazada desde el medio hasta el orden de izquierda a derecha usando la recursividad.
Por ejemplo:
Si la lista enlazada dada es: 2 -> 5 -> 8 -> 3 -> 7 -> 9 -> 12 -> NULL
El orden medio a izquierda-derecha es: 3, 8, 7, 5, 9, 2, 12
Explicación: El medio de la lista enlazada dada es ‘3’, entonces, comenzamos a atravesar desde el medio imprimiendo 3, luego a la izquierda y a la derecha de 3, por lo que imprimimos 8, 7, luego imprimimos a la izquierda de 8 y a la derecha de 7, por lo que imprimimos 5, 9 luego imprima a la izquierda de 5 y a la derecha de 9, por lo que imprimimos 2, 12.
Nota: si el número de Nodes es par en una lista enlazada, imprima solo de izquierda a derecha. Para esta lista enlazada (contiene un número par de Nodes) 2 -> 5 -> 8 -> 7 -> 9 -> 12 -> NULL.
La salida debe ser 8, 7, 5, 9, 2, 12.
Ejemplos:
Entrada: 20 -> 15 -> 23 -> 13 -> 19 -> 32 -> 16 -> 41 -> 11 -> NULO
Salida: 19, 13, 32, 23, 16, 15, 41, 20, 11.
Entrada: 12 -> 25 -> 51 -> 16 -> 9 -> 90 -> 7 -> 2 -> NULL
Salida: 16, 9, 51, 90, 25, 7, 12, 2.
Enfoque:
Primero, calcule el tamaño de la lista enlazada:
- Si el tamaño es impar:
-> Luego vaya al (n+1)/2 -ésimo Node usando recursividad. - Si el tamaño es par:
-> Luego vaya al n/2 -th Node usando recursividad. - Ahora imprima los datos del Node y devuelva la siguiente dirección del Node, realice este procedimiento a menos que la función llame a la pila vacía.
A continuación se muestra la implementación del enfoque anterior:
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 node
class 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 end
void 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 head
void printList(Node* node)
{
while (node != NULL) {
cout << " " << node->data;
if (node->next != NULL)
cout << "->";
node = node->next;
}
}
// Function to get the size of linked list
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 order
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
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 order
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
cout << "Output : ";
printMiddleToLeftRightUtil(head,
middle,
listSize);
}
// Driver code
int 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 order
class GFG
{
// A linked list node
static 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 end
static 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 head
static 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 list
static 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 order
static 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 order
static 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 code
public 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 node
class 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 end
def 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 list
def getSize(head):
if (head == None):
return 0;
return 1 + getSize(head.next);
# Utility function to print the Linked List
# from middle to left right order
def 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 order
def 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 code
if __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 order
using System;
public class GFG
{
// A linked list node
public 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 end
static 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 head
static 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 list
static 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 order
static 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 order
static 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 code
public 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 list
class 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 end
function 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 head
function 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 list
function getSize( head)
{
if (head == null)
return 0;
return 1 + getSize(head.next);
}
// Utility function to print the Linked List
// from middle to left right order
function 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 order
function 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 list
var 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
document.write("Created Linked list is: ");
// Function to display Linked List content
printList(head);
document.write("</br>");
// Function call print Linked List from
// Middle to left right order
printMiddleToLeftRight(head);
</script>
Producción:
Created Linked list is: 6-> 4-> 8-> 7-> 9-> 11-> 2 Output : 7 , 8 , 9 , 4 , 11 , 6 , 2
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA