Find middle of singly linked list using recursion
In this problem, we are given a singly linked list and our task is to find and print the middle element of the linked list using recursion. The middle element is the one that lies exactly in the middle of the linked list. If the linked list has an odd number of elements, there will be only one middle element. If the linked list has an even number of elements, there will be two middle elements, and we will consider the second one as the middle for this case.
Problem Statement
Given a singly linked list, we need to find and print the middle element(s) of the linked list using recursion.
Example Scenario
Let's consider two linked lists:
 Linked List A: 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
 Linked List B: 4 → 9 → 7 → 3 → 8 → 6 → NULL
For Linked List A, the middle node is 4. For Linked List B, the middle node is 7.
Idea to Solve the Problem
To solve this problem, we can use a recursive approach. We can implement a recursive function that takes two pointers as arguments: one that moves one step at a time (slow pointer) and another that moves two steps at a time (fast pointer). By the time the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle element of the list.
Pseudocode
class LinkNode:
int data
LinkNode next
LinkNode(data):
this.data = data
this.next = null
class SingleLL:
LinkNode head
LinkNode tail
// Constructor and other methods...
function printMiddle(node, mid):
if node is not null and node.next is not null and node.next.next is not null:
// Recursive call with fast pointer moving two steps and slow pointer moving one step
printMiddle(node.next.next, mid.next)
else:
// Base case: when fast pointer reaches the end, print middle element
print("Middle Node:", mid.data)
function findMiddle():
if this.head is null:
print("Empty Linked List")
else if this.head.next is null:
print("Linked list contains only one node")
else:
print("Linked List:")
display()
printMiddle(this.head, this.head)
// Main function
sll1 = SingleLL()
sll1.addNode(1)
sll1.addNode(2)
// Add other nodes...
sll1.findMiddle()
sll2 = SingleLL()
sll2.addNode(4)
sll2.addNode(9)
// Add other nodes...
sll2.findMiddle()
Algorithm Explanation
 Define a recursive function
printMiddle
that takes two pointers:node
(fast pointer) andmid
(slow pointer) as arguments.  Inside the function, check if the current
node
and its next two nodes are not null. If true, make a recursive call withnode.next.next
andmid.next
to move the pointers accordingly.  If the above condition is false, it means the fast pointer has reached the end of the list. Print the middle
node's data using the
mid
pointer.  In the
findMiddle
function, check for different cases such as an empty linked list, a single node, and a general case.  Call the
printMiddle
function with appropriate pointers and display the result.
Code Solution

1) Print middle element of linked list using recursion in java
2) Print middle element of linked list using recursion in c++
3) Print middle element of linked list using recursion in c
4) Print middle element of linked list using recursion in c#
5) Print middle element of linked list using recursion in vb.net
6) Print middle element of linked list using recursion in php
7) Print middle element of linked list using recursion in node js
8) Print middle element of linked list using recursion in typescript
9) Print middle element of linked list using recursion in python
10) Print middle element of linked list using recursion in ruby
11) Print middle element of linked list using recursion in scala
12) Print middle element of linked list using recursion in swift
13) Print middle element of linked list using recursion in kotlin
14) Print middle element of linked list using recursion in golang
Time Complexity
The time complexity of finding the middle element of a singly linked list using recursion is O(n), where n is the number of nodes in the linked list. This is because the recursive function makes one pass through the entire linked list to find the middle element.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment