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

Let's consider two linked lists:

  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

Print middle node of linked list

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

  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.

Code Solution

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.

New Comment