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