876. Middle of the Linked List

EasyLinked ListTwo Pointers
Leetcode Link

Problem Description

The task is to write a function that, given the head of a singly linked list, finds and returns the middle node of the list. A singly linked list is a collection of nodes where each node contains a value and a reference to the next node in the sequence. The key characteristic of this list is that you can only traverse it in one direction: from the head towards the end.

The challenge here is determining the middle node in a single pass, since the size of the list is not given in advance. It's also specified that if the linked list has an even number of nodes, we should return the second of the two middle nodes.

Intuition

To solve this problem efficiently, we make use of two pointers: slow and fast. Both pointers start at the head of the linked list. The fast pointer moves through the list at twice the speed of the slow pointer. This means that for every node the slow pointer travels, the fast pointer moves two nodes.

As a result of these different speeds, when the fast pointer reaches the end of the list, the slow pointer will be positioned at the middle. This happens because the fast pointer traverses two nodes for every single step taken by the slow pointer. If the total number of nodes is odd, the fast pointer will eventually point to None, which is the end of the list. If the number of nodes is even, the fast pointer will point to the last node. In both cases, the slow pointer will be at the middle, where if there are two middle nodes, because fast moves two steps at a time, slow will end up at the second middle node.

This approach allows us to find the middle node in a single pass through the list, which is more efficient than first counting the nodes and then traversing again to the middle—especially in the case of very large lists.

Learn more about Linked List and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The given solution makes use of two pointers, slow and fast, both initialized to the head of the list. This approach is commonly known as the "tortoise and hare" algorithm. Let's go through the steps of this approach:

  1. Both slow and fast are initialized at the head of the linked list, thus they start at the same position.

  2. We then enter a loop that continues until fast is no longer pointing to a valid node or fast.next is None. This condition ensures that we stop when fast (which moves faster) has reached the end of the list.

  3. Inside the loop, slow is incremented to the next node (slow.next) and fast is incremented two nodes ahead (fast.next.next).

    • slow = slow.next moves the slow pointer one step forward.
    • fast = fast.next.next moves the fast pointer two steps forward.

  4. When fast reaches the end of the list or there are no more nodes to traverse (fast becomes None or fast.next is None), the loop ends.

  5. At this point, slow will be at the middle node of the list. If there are an odd number of nodes, it will be the exact middle. If there are an even number of nodes, it will be the second of the two middle nodes because of the way fast is moving two steps at a time.

  6. The function then returns the slow pointer, which now points to the middle node of the linked list.

No additional data structure is used, making the space complexity O(1), as we only have two pointers regardless of the size of the linked list. Since each node is visited once by either slow or fast, the time complexity is O(n), where n is the number of nodes in the list.

The beauty of this solution lies in its simplicity and efficiency. It effectively halves the traversal time to find the middle node, which would otherwise take longer if we first counted the entire list to find the length, and then iterated again to the middle.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Suppose we have a singly linked list with 7 nodes, and their values when traversed from head to tail are [1, 2, 3, 4, 5, 6, 7]. We want to determine the middle node in a single pass.

We initialize two pointers at the start, slow points to the node with the value 1, and fast also points to the node with value 1.

As we loop through the list:

  • In the first step, slow will move one node and point to 2; fast will move two nodes and point to 3.
  • In the second step, slow will move to 3; fast to 5.
  • In the third step, slow moves to 4, fast moves to 7.
  • Now, fast is pointing at the last node, and fast.next is None. Thus, we reach the condition to end the loop.

At this point, slow is pointing to 4, which is the middle node in this list of 7 nodes. Our function would then return the node with the value 4 as the middle node.

Now, let's consider an even-numbered list with 6 nodes, where the values are [1, 2, 3, 4, 5, 6].

  • On starting, both slow and fast point to 1.
  • In the first step, slow moves to 2; fast jumps to 3.
  • In the second step, slow goes to 3; fast skips to 5.
  • In the third step, slow proceeds to 4 and fast jumps to the last node, 6.
  • fast.next is now None. The loop ends.

Slow is at the value 4, which is the second of the two middle nodes in this list of 6 nodes, meeting our requirement to return the second middle node in the case of an even-numbered list.

With this explanation, it should be clear how the "tortoise and hare" algorithm functions, allowing us to find the middle of the list in a single pass, hence delivering an efficient solution.

Solution Implementation

1# Class definition for a singly-linked list node.
2class ListNode:
3    def __init__(self, value=0, next_node=None):
4        self.value = value
5        self.next_node = next_node
6
7class Solution:
8    def middleNode(self, head: ListNode) -> ListNode:
9        # Initialize two pointers, both starting at the head of the list.
10        # 'slow' will move one step at a time, and 'fast' will move two steps at a time.
11        slow_pointer = fast_pointer = head
12      
13        # Traverse the list. The loop runs until 'fast' reaches the end of the list.
14        while fast_pointer and fast_pointer.next_node:
15            # Move 'slow' one step forward.
16            slow_pointer = slow_pointer.next_node
17            # Move 'fast' two steps forward.
18            fast_pointer = fast_pointer.next_node.next_node
19      
20        # When 'fast' reaches the end, 'slow' will be at the middle node.
21        return slow_pointer
22
1// Definition for singly-linked list.
2class ListNode {
3    int value;
4    ListNode next;
5  
6    // Constructor with no parameters
7    ListNode() {}
8  
9    // Constructor with value parameter
10    ListNode(int value) {
11        this.value = value;
12    }
13  
14    // Constructor with value and next node parameters
15    ListNode(int value, ListNode next) {
16        this.value = value;
17        this.next = next;
18    }
19}
20
21public class Solution {
22  
23    /**
24     * Finds the middle node of a singly linked list.
25     * 
26     * @param head The head of the linked list.
27     * @return The middle node of the linked list.
28     */
29    public ListNode middleNode(ListNode head) {
30        // Initialize two pointers, slow and fast.
31        ListNode slowPointer = head;
32        ListNode fastPointer = head;
33      
34        // Iterate through the list.
35        // Fast pointer moves two steps at a time, slow pointer one step at a time.
36        while (fastPointer != null && fastPointer.next != null) {
37            slowPointer = slowPointer.next;       // Move slow pointer one step
38            fastPointer = fastPointer.next.next;  // Move fast pointer two steps
39        }
40      
41        // When fast pointer reaches the end of the list,
42        // slow pointer will be at the middle element.
43        return slowPointer;
44    }
45}
46
1/**
2 * Definition for a singly-linked list node.
3 */
4struct ListNode {
5    int val;           // The value the node stores
6    ListNode *next;    // Pointer to the next list node in the linked list
7
8    // Constructor to initialize a node with no next node
9    ListNode() : val(0), next(nullptr) {}
10
11    // Constructor to initialize a node with a specific value and no next node
12    ListNode(int x) : val(x), next(nullptr) {}
13
14    // Constructor to initialize a node with a specific value and a next node
15    ListNode(int x, ListNode *next) : val(x), next(next) {}
16};
17
18class Solution {
19public:
20    /**
21     * Finds the middle node of a singly linked list.
22     * If there are two middle nodes, the second middle node is returned.
23     * 
24     * @param head The head of the linked list.
25     * @return The middle node of the linked list
26     */
27    ListNode* middleNode(ListNode* head) {
28        ListNode *slow = head; // 'slow' pointer moves one node at a time
29        ListNode *fast = head; // 'fast' pointer moves two nodes at a time
30
31        // Continue until 'fast' reaches the end of the list
32        while (fast != nullptr && fast->next != nullptr) {
33            slow = slow->next;         // Move 'slow' by one node
34            fast = fast->next->next;   // Move 'fast' by two nodes
35        }
36      
37        // When 'fast' reaches the end, 'slow' will be at the middle node
38        return slow;
39    }
40};
41
1// Definition for singly-linked list node.
2interface ListNode {
3    val: number;
4    next: ListNode | null;
5}
6
7/**
8 * Finds the middle node of a singly linked list.
9 * @param head The head of the singly linked list.
10 * @return The middle node of the list.
11 */
12function middleNode(head: ListNode | null): ListNode | null {
13    let fastPointer: ListNode | null = head; // Pointer that will move two steps at a time
14    let slowPointer: ListNode | null = head; // Pointer that will move one step at a time
15
16    // Loop until the fast pointer reaches the end of the list
17    while (fastPointer !== null && fastPointer.next !== null) {
18        fastPointer = fastPointer.next.next; // Move fast pointer two steps
19        slowPointer = slowPointer.next;      // Move slow pointer one step
20    }
21
22    // When the fast pointer reaches the end of the list,
23    // the slow pointer will be at the middle
24    return slowPointer;
25}
26
Not Sure What to Study? Take the 2-min Quiz：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the linked list. This is because the fast pointer advances two steps at a time and the slow pointer advances one step at a time. They start at the same point, so when the fast pointer reaches the end of the list, the slow pointer must be at the middle. Since the fast pointer traverses at most n nodes (where n is even) or n-1 nodes (where n is odd), and it takes two iterations of the loop to move the fast pointer two nodes ahead, the loop executes approximately n/2 iterations, which is linear with respect to the number of nodes.

The space complexity is O(1) irrespective of the number of nodes in the linked list because only two additional pointers (variables slow and fast) are used, which occupy constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫