Middle Of The Linked List

Middle of the Linked List

Difficulty: Easy

Understanding the Problem

Problem Description

Given a non-empty, singly linked list with head node head , write a program to return a middle node of the linked list. If there are even nodes, then there would be two middle nodes, we need to print the second middle element.

Example 1

Input: 11->2->13->44->5 
Output: 13
Explanation: The middle element of the linked list is 13.

Example 2

Input: 10->2->34->24->15->60 
Output: 24
Explanation: As there are even number of nodes, return 24 as it is the second node among two middle elements.

Solutions

Two-Pass: Find the length of the linked list and return the (length/2)th node.
One-Pass: Use two pointers, the 2nd pointer should traverse twice as fast at the first.

Before moving forward with the question, you must understand the properties of a linked list .

You can try this problem here.

1. Two-Pass

The question demands to find the middle of a singly linked list. We can simply find the total length of the linked list, in this way we can identify which node falls in the middle. To find the middle node, we can traverse again until we reach (length/2)th node.

Solution Steps

Create a pointer p , pointing to the head.
Iterate over the linked list until p reaches to the end of the linked list, thereby find the length of the list.
Set p to head again. Now, increment p length/2 times. Now, the p is at the middle of the linked list node. Return the value at p

Pseudo Code

int middleNode(ListNode head) {
    int l=0
    ListNode p = head
    while (p != null) {
        p = p.next
        l = l + 1
    }
    p = head
    int c = 0
    while (c < l/2) {
        p = p.next
        c = c + 1
    }
    return p.data
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas To Think

Why did we reinitialize p with the head ?
Which node will be returned if the length of the linked list is even?
What if the linked list forms a loop?

2. One-Pass

Another way to solve this problem is to use a little trick. Instead of traversing twice, we can create two-pointers say slow_ptr and fast_ptr. We can make the fast_ptr twice as fast as slow_ptr . So, When the fast_ptr will reach to the end of the linked list, slow_ptr would still be at the middle, thereby pointing to the mid of the linked list.

Solutions Steps

Create slow_ptr and fast_ptr pointing to the head initially.
Increment fast_ptr by 2 and slow_ptr by 1 positions until fast_ptr and fast_ptr.next is not NULL
Return the value at slow_ptr .

Pseudo Code

int middleNode(ListNode head) {
    ListNode slow = head
    ListNode fast = head
    while (fast != null and fast.next != null) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow.data
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas To Think