Encuentra el medio de una lista enlazada individualmente Recursivamente

Dada una lista enlazada individualmente y la tarea es encontrar el medio de la lista enlazada. 
Ejemplos: 
 

Input  : 1->2->3->4->5  
Output : 3

Input  : 1->2->3->4->5->6
Output : 4

Ya hemos discutido la solución iterativa . En esta publicación se discute la solución iterativa. Cuente el número total de Nodes en la lista de manera recursiva y haga la mitad de esto, suponga que este valor es n. Luego retrocede a través del decremento de recursión n en uno para cada llamada. Devuelve el Node donde n es cero. 
 

C++

// C++ program for Recursive approach to find
// middle of singly linked list
#include <iostream>
using namespace std;
 
// Tree Node Structure
struct Node
{
    int data;
    struct Node* next;
};
 
// Create new Node
Node* newLNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
 
// Function for finding midpoint recursively
void midpoint_util(Node* head, int* n, Node** mid)
{
 
    // If we reached end of linked list
    if (head == NULL)
    {
        *n = (*n) / 2;
        return;
    }
 
    *n = *n + 1;
 
    midpoint_util(head->next, n, mid);
 
    // Rolling back, decrement n by one
    *n = *n - 1;
    if (*n == 0)
    {
 
        // Final answer
        *mid = head;
    }
}
 
Node* midpoint(Node* head)
{
    Node* mid = NULL;
    int n = 1;
    midpoint_util(head, &n, &mid);
    return mid;
}
 
int main()
{
    Node* head = newLNode(1);
    head->next = newLNode(2);
    head->next->next = newLNode(3);
    head->next->next->next = newLNode(4);
    head->next->next->next->next = newLNode(5);
    Node* result = midpoint(head);
    cout << result->data << endl;
    return 0;
}

Java

// Java program for Recursive approach to find
// middle of singly linked list
class GFG
{
 
// Tree Node Structure
static class Node
{
    int data;
    Node next;
};
 
// Create new Node
static Node newLNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.next = null;
    return temp;
}
 
static int n;
static Node mid;
 
// Function for finding midpoint recursively
static void midpoint_util(Node head )
{
 
    // If we reached end of linked list
    if (head == null)
    {
        n = (n) / 2;
        return;
    }
 
    n = n + 1;
 
    midpoint_util(head.next);
 
    // Rolling back, decrement n by one
    n = n - 1;
    if (n == 0)
    {
 
        // Final answer
        mid = head;
    }
}
 
static Node midpoint(Node head)
{
    mid = null;
    n = 1;
    midpoint_util(head);
    return mid;
}
 
// Driver code
public static void main(String args[])
{
    Node head = newLNode(1);
    head.next = newLNode(2);
    head.next.next = newLNode(3);
    head.next.next.next = newLNode(4);
    head.next.next.next.next = newLNode(5);
    Node result = midpoint(head);
    System.out.print( result.data );
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program for Recursive approach
# to find middle of singly linked list
 
# Node class
class Node:
 
    # Function to initialise the node object
    def __init__(self, data):
        self.data = data
        self.next = None
         
# Create new Node
def newLNode(data):
 
    temp = Node(data)
    temp.data = data
    temp.next = None
    return temp
 
mid = None
n = 0
 
# Function for finding midpoint recursively
def midpoint_util(head ):
 
    global n
    global mid
     
    # If we reached end of linked list
    if (head == None):
     
        n = int((n) / 2)
        return
     
    n = n + 1
 
    midpoint_util(head.next)
 
    # Rolling back, decrement n by one
    n = n - 1
    if (n == 0):
     
        # Final answer
        mid = head
 
def midpoint(head):
 
    global n
    global mid
     
    mid = None
    n = 1
    midpoint_util(head)
    return mid
 
# Driver Code
if __name__=='__main__':
     
    head = newLNode(1)
    head.next = newLNode(2)
    head.next.next = newLNode(3)
    head.next.next.next = newLNode(4)
    head.next.next.next.next = newLNode(5)
    result = midpoint(head)
    print( result.data )
     
# This code is contributed by Arnab Kundu

C#

// C# program for Recursive approach to find
// middle of singly linked list
using System;
class GFG
{
 
// Tree Node Structure
public class Node
{
    public int data;
    public Node next;
};
 
// Create new Node
static Node newLNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.next = null;
    return temp;
}
 
static int n;
static Node mid;
 
// Function for finding midpoint recursively
static void midpoint_util(Node head )
{
 
    // If we reached end of linked list
    if (head == null)
    {
        n = (n) / 2;
        return;
    }
 
    n = n + 1;
 
    midpoint_util(head.next);
 
    // Rolling back, decrement n by one
    n = n - 1;
    if (n == 0)
    {
 
        // Final answer
        mid = head;
    }
}
 
static Node midpoint(Node head)
{
    mid = null;
    n = 1;
    midpoint_util(head);
    return mid;
}
 
// Driver code
public static void Main()
{
    Node head = newLNode(1);
    head.next = newLNode(2);
    head.next.next = newLNode(3);
    head.next.next.next = newLNode(4);
    head.next.next.next.next = newLNode(5);
    Node result = midpoint(head);
    Console.WriteLine( result.data );
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for Recursive approach to find
// middle of singly linked list
 
// Tree Node Structure
class Node
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
};
 
// Create new Node
function newLNode(data)
{
    var temp = new Node();
    temp.data = data;
    temp.next = null;
    return temp;
}
 
var n = 0;
var mid = null;;
 
// Function for finding midpoint recursively
function midpoint_util(head)
{
 
    // If we reached end of linked list
    if (head == null)
    {
        n = (n) / 2;
        return;
    }
 
    n = n + 1;
 
    midpoint_util(head.next);
 
    // Rolling back, decrement n by one
    n = n - 1;
    if (n == 0)
    {
 
        // Final answer
        mid = head;
    }
}
 
function midpoint(head)
{
    mid = null;
    n = 1;
    midpoint_util(head);
    return mid;
}
 
// Driver code
var head = newLNode(1);
head.next = newLNode(2);
head.next.next = newLNode(3);
head.next.next.next = newLNode(4);
head.next.next.next.next = newLNode(5);
var result = midpoint(head);
document.write( result.data );
 
</script>

Producción:  

3

Publicación traducida automáticamente

Artículo escrito por Anivesh Tiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *