给定一个单链表，任务是找到链表的中间部分。 例如：
null
Input : 1->2->3->4->5 Output : 3Input : 1->2->3->4->5->6Output : 4
我们已经讨论过了 迭代解法 .本文讨论了迭代后的解。以递归方式计算列表中的节点总数，并将其减半，假设该值为n。然后通过递归将n减量为每次调用减量1进行回滚。返回n为零的节点。
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> |
输出：
3
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
