#876

Easy

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Middle of the Linked List

Find the middle node of a singly linked list using a two-pointer technique.

Problem Statement

Given a singly linked list, return the middle node. If the list has an even number of nodes, return the second of the two middle nodes.

For example, given a list of nodes [1, 2, 3, 4, 5], the middle node is 3. For a list [1, 2, 3, 4, 5, 6], the second middle node is 4.

Examples

Example 1

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

Output: [3,4,5]

The middle node of the list is node 3.

Example 2

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

Output: [4,5,6]

Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints

The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100

Solution Approach

Two-pointer Approach

Use two pointers: one moves two steps at a time and the other moves one step. When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Edge Case Handling

Ensure that the solution handles lists of various lengths, including lists with only one node, which is trivially the middle.

Return the Correct Middle Node

If the list has an even number of nodes, return the second middle node as required by the problem statement.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n) because we traverse the list once, where n is the number of nodes in the list. The space complexity is O(1) since we use a constant amount of extra space, only maintaining two pointers.

What Interviewers Usually Probe

Ensure the candidate can explain the two-pointer technique and its efficiency.
Look for a solid understanding of edge cases like a list with a single node or an even-length list.
Evaluate if the candidate can discuss how pointer manipulation works in the context of linked lists.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling even-length lists by returning the first middle node instead of the second.
Failing to properly set up the two-pointer technique, leading to incorrect traversal of the list.
Not addressing edge cases, like lists with only one node.

Follow-up variants

Finding the middle node using an iterative approach instead of two pointers.
Using a recursive approach to find the middle node in the list.
Returning the middle node's value instead of the node itself.

FAQ

How do I solve the 'Middle of the Linked List' problem?

The best approach is the two-pointer technique: one pointer moves two steps at a time, and the other moves one step. The slower pointer reaches the middle when the fast one reaches the end.

What if the list has an even number of nodes?

If the list has two middle nodes, you must return the second one. For example, with the list [1, 2, 3, 4], return 3.

What is the time complexity of the two-pointer solution?

The time complexity is O(n), where n is the number of nodes in the linked list, since we traverse the list once.

Are there any edge cases to consider for this problem?

Yes, the list could have one node, which is trivially the middle. Also, an even-length list should return the second middle node.

How does the two-pointer technique work?

The two-pointer technique uses two pointers: one moves two steps at a time, and the other moves one step at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

terminal

Solution

Solution 1: Fast and Slow Pointers

We define two pointers $\textit{fast}$ and $\textit{slow}$, both initially pointing to the head of the linked list.

1

2

3

4

5

6

7

8

9

10

11

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        return slow

Continue Practicing

#234 palindrome linked list #160 intersection of two linked lists #148 sort list