Jobs

Interviews

Discussions

Middle of the Linked List

Easy

Amazon

4 views

Topics:

Linked ListsTwo Pointers

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

For example:

Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]

Explain two different approaches to solve this problem, and detail the time and space complexity. Be sure to explain any edge cases.

Middle of the Linked List

Easy

Amazon

4 views

Topics:

Linked ListsTwo Pointers

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

For example:

Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]

Explain two different approaches to solve this problem, and detail the time and space complexity. Be sure to explain any edge cases.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty, and if so, what should I return?
What is the data type of the values stored in the linked list nodes?
By 'second middle node', do you mean that if the list has an even number of nodes, I should return the node at index `n/2` (where `n` is the number of nodes and the head is at index 0)?
Are there any constraints on the size (number of nodes) of the linked list?
Can I assume the linked list is properly formed (no cycles or other anomalies)?

Brute Force Solution

Approach

The brute force method for finding the middle of a linked list is like figuring out which item is in the middle of a train without knowing how many train cars there are. We will walk through the entire train step by step.

Here's how the algorithm would work step-by-step:

First, we'll count how many train cars there are by starting at the front and visiting each car until we reach the end.
Once we know the total number of train cars, we can calculate the middle position.
Next, we'll go back to the front of the train.
We'll travel from the front to the middle position, one train car at a time.
When we arrive at that middle position, that's the train car we're looking for.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def find_middle_brute_force(head):
    list_length = 0
    current_node = head

    # Iterate through the list to get the length
    while current_node:
        list_length += 1
        current_node = current_node.next_node

    middle_index = list_length // 2
    current_node = head
    current_index = 0

    # Traverse the list until the middle is found
    while current_index < middle_index:
        current_node = current_node.next_node
        current_index += 1

    return current_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm first traverses the linked list to determine its length, which takes O(n) time, where n is the number of nodes in the list. Then, it traverses the list again, this time stopping at the middle node. This second traversal takes O(n/2) time. The total time is therefore O(n) + O(n/2), which simplifies to O(n) because we drop constant factors in Big O notation.

Space Complexity

O(1) – The brute force method only uses a few integer variables: one to store the total number of train cars (nodes in the linked list) and another to keep track of the current position when traversing to the middle. The space required for these variables is constant and does not depend on the size of the linked list (N, where N is the number of nodes). Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We can find the middle of a linked list without knowing its total size beforehand by using two 'pointers' that move at different speeds. This cleverly allows us to reach the middle in a single pass through the list.

Here's how the algorithm would work step-by-step:

Imagine you have two runners starting at the beginning of the linked list.
One runner moves one step at a time, while the other runner moves two steps at a time.
When the faster runner reaches the end of the linked list, the slower runner will be exactly in the middle.
So, keep moving both runners until the faster runner can't move two steps anymore.
At that point, the slower runner is pointing to the middle of the linked list.

Code Implementation

def middle_node(head):
    slow_pointer = head
    fast_pointer = head

    # Traverse list with slow_pointer moving 1 step and fast_pointer moving 2 steps
    while fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next
        fast_pointer = fast_pointer.next.next

    #When fast_pointer reaches the end, slow_pointer will be at the middle
    return slow_pointer

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next = next_node

# Example Usage (Not part of the solution, for testing purposes only)
if __name__ == '__main__':
    # Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
    head_node = ListNode(1)
    head_node.next = ListNode(2)
    head_node.next.next = ListNode(3)
    head_node.next.next.next = ListNode(4)
    head_node.next.next.next.next = ListNode(5)

    middle = middle_node(head_node)
    print(middle.value)  # Output: 3

    # Create another list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    head_node = ListNode(1)
    head_node.next = ListNode(2)
    head_node.next.next = ListNode(3)
    head_node.next.next.next = ListNode(4)
    head_node.next.next.next.next = ListNode(5)
    head_node.next.next.next.next.next = ListNode(6)

    middle = middle_node(head_node)
    print(middle.value) # Output: 4

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm iterates through the linked list using two pointers, a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. The loop continues until the fast pointer reaches the end of the linked list. Therefore, the slow pointer traverses half the list. Since the fast pointer visits each node (at most) twice, the time complexity is directly proportional to the number of nodes, n, in the linked list. Hence, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm uses two pointers, often called 'slow' and 'fast', to traverse the linked list. These pointers are simply references to nodes within the existing list and do not create any new data structures proportional to the input size, N, which represents the number of nodes in the linked list. Since we are only storing a fixed number of pointer variables, the auxiliary space used remains constant regardless of the size of the linked list. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty linked list (head is null)	Return null immediately as there is no middle node in an empty list.
Single-node linked list	Return the head node itself, as it's the middle node.
Two-node linked list	Return the second node, fulfilling the requirement to return the 'second' middle node in case of even length.
Large linked list (potential performance concerns)	The fast and slow pointer approach has O(n) time complexity and constant space complexity, scaling efficiently.
Linked list with duplicate values	The values within the nodes are irrelevant to finding the middle node using the fast/slow pointer approach.
Linked list with a very long length near integer limit for storing length	The fast and slow pointer approach avoids storing the length, preventing overflow issues.
Linked list with negative, zero, and positive values	Node values do not affect the algorithm, so it works fine with any value.
Memory limitations prevent creating a large array to store node values.	The fast/slow pointer method uses constant space, avoiding memory limitations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty, and if so, what should I return?
What is the data type of the values stored in the linked list nodes?
By 'second middle node', do you mean that if the list has an even number of nodes, I should return the node at index `n/2` (where `n` is the number of nodes and the head is at index 0)?
Are there any constraints on the size (number of nodes) of the linked list?
Can I assume the linked list is properly formed (no cycles or other anomalies)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we'll count how many train cars there are by starting at the front and visiting each car until we reach the end.
Once we know the total number of train cars, we can calculate the middle position.
Next, we'll go back to the front of the train.
We'll travel from the front to the middle position, one train car at a time.
When we arrive at that middle position, that's the train car we're looking for.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def find_middle_brute_force(head):
    list_length = 0
    current_node = head

    # Iterate through the list to get the length
    while current_node:
        list_length += 1
        current_node = current_node.next_node

    middle_index = list_length // 2
    current_node = head
    current_index = 0

    # Traverse the list until the middle is found
    while current_index < middle_index:
        current_node = current_node.next_node
        current_index += 1

    return current_node

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have two runners starting at the beginning of the linked list.
One runner moves one step at a time, while the other runner moves two steps at a time.
When the faster runner reaches the end of the linked list, the slower runner will be exactly in the middle.
So, keep moving both runners until the faster runner can't move two steps anymore.
At that point, the slower runner is pointing to the middle of the linked list.

Code Implementation

def middle_node(head):
    slow_pointer = head
    fast_pointer = head

    # Traverse list with slow_pointer moving 1 step and fast_pointer moving 2 steps
    while fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next
        fast_pointer = fast_pointer.next.next

    #When fast_pointer reaches the end, slow_pointer will be at the middle
    return slow_pointer

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next = next_node

# Example Usage (Not part of the solution, for testing purposes only)
if __name__ == '__main__':
    # Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
    head_node = ListNode(1)
    head_node.next = ListNode(2)
    head_node.next.next = ListNode(3)
    head_node.next.next.next = ListNode(4)
    head_node.next.next.next.next = ListNode(5)

    middle = middle_node(head_node)
    print(middle.value)  # Output: 3

    # Create another list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    head_node = ListNode(1)
    head_node.next = ListNode(2)
    head_node.next.next = ListNode(3)
    head_node.next.next.next = ListNode(4)
    head_node.next.next.next.next = ListNode(5)
    head_node.next.next.next.next.next = ListNode(6)

    middle = middle_node(head_node)
    print(middle.value) # Output: 4

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty linked list (head is null)	Return null immediately as there is no middle node in an empty list.
Single-node linked list	Return the head node itself, as it's the middle node.
Two-node linked list	Return the second node, fulfilling the requirement to return the 'second' middle node in case of even length.
Large linked list (potential performance concerns)	The fast and slow pointer approach has O(n) time complexity and constant space complexity, scaling efficiently.
Linked list with duplicate values	The values within the nodes are irrelevant to finding the middle node using the fast/slow pointer approach.
Linked list with a very long length near integer limit for storing length	The fast and slow pointer approach avoids storing the length, preventing overflow issues.
Linked list with negative, zero, and positive values	Node values do not affect the algorithm, so it works fine with any value.
Memory limitations prevent creating a large array to store node values.	The fast/slow pointer method uses constant space, avoiding memory limitations.