Intuition

The problem is to identify the middle element or node of the given Singly Linked List and return second middle element if the length of List is even. Basically there are two approaches to solve this problem:

• Approach 1: Brute Force $$$TC:O(N) + O(N/2)$$$
• Approach 2: Tortoise Rabbit Algorithm $$$TC:O(N/2)$$$

Approach 1

In the Brute Force approach, we will be calculating the length of Linked List by traversing through each element using temp pointer. Then calculate the half of length ($$$length/2$$$). Once again traverse through the Linked List and move the head variable until half of its length is reached, after reaching return the head pointer. Now the head pointer contains the chain from middle element of that List.

• Time complexity: O(N) + O(N/2)
• Space complexity: O(K)

Code

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* ptr = head;
    int length=0;
    int mid;

    while(ptr != NULL){
        ptr = ptr->next;
        length++;
    }

    mid = length/2;
    while(mid--){
            head = head->next;
    }

    return head;
}

Result

Runtime: 2ms Memory: 6MB

Approach 2

By using Tortoise Rabbit Algorithm, initially we assign two pointers tortoise and rabbit to head node. Now, we move both the pointers in such a way that Tortoise pointer moves one step forward asusual and Rabbit pointer moves two steps forward. So, when the Rabbit pointer reaches the end of List or the last node of List we have Tortoise pointer at the middle node of the List. Then we return the Tortoise pointer which contains the chain from middle element of the List.

• Time complexity: O(N/2)
• Space complexity: O(K)

Code

// In C
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *tortoise = head;
    struct ListNode *rabbit = head;

    while(rabbit != NULL && rabbit->next != NULL){
        tortoise = tortoise->next;
        rabbit = rabbit->next->next;
    }

    return tortoise;
}

// In Java
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode tortoise = head;
        ListNode rabbit = head;

        while(rabbit != null && rabbit.next != null){
            tortoise = tortoise.next;
            rabbit = rabbit.next.next;
        }

        return tortoise;
    }
}

Result

Runtime: 0ms Memory: 6MB

Upvote the solution, if you like the appraoch!