Posted on by Kalkicode
Code Recursion

# 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

1. Linked List A: 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
2. 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
this.data = data
this.next = null

class SingleLL:

// 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():
print("Linked list contains only one node")
else:
display()

// Main function
sll1 = SingleLL()
sll1.findMiddle()

sll2 = SingleLL()
sll2.findMiddle()``````

## Algorithm Explanation

1. Define a recursive function `printMiddle` that takes two pointers: `node` (fast pointer) and `mid` (slow pointer) as arguments.
2. Inside the function, check if the current `node` and its next two nodes are not null. If true, make a recursive call with `node.next.next` and `mid.next` to move the pointers accordingly.
3. 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.
4. In the `findMiddle` function, check for different cases such as an empty linked list, a single node, and a general case.
5. Call the `printMiddle` function with appropriate pointers and display the result.

## 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.

## Comment

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.

Categories
Relative Post