876. Middle of the Linked List - Explanation

Description

You are 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.

Example 1:

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

Output: [3,4,5]

Example 2:

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

Output: [4,5,6]

Constraints:

1 <= The length of the list <= 100
1 <= Node.val <= 100

Topics

Linked List Two Pointers

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Linked Lists - Understanding node structure with value and next pointer, and how to traverse a linked list
Two Pointers (Fast & Slow) - The technique of using two pointers moving at different speeds to find middle elements or detect cycles
Arrays - Using dynamic arrays to store elements for indexed access

1. Convert To Array

Intuition

Linked lists do not support random access, so finding the middle node directly is not straightforward. By storing all nodes in an array, we gain index-based access. Once we have the array, the middle node is simply at index length / 2.

Algorithm

Traverse the linked list and store each node in an array.
Calculate the middle index as length / 2.
Return the node at the middle index.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        arr = []
        while cur:
            arr.append(cur)
            cur = cur.next
        return arr[len(arr) // 2]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode middleNode(ListNode head) {
        ArrayList<ListNode> arr = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size() / 2);
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> arr;
        ListNode* cur = head;
        while (cur) {
            arr.push_back(cur);
            cur = cur->next;
        }
        return arr[arr.size() / 2];
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    middleNode(head) {
        let arr = [];
        let cur = head;
        while (cur) {
            arr.push(cur);
            cur = cur.next;
        }
        return arr[Math.floor(arr.length / 2)];
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MiddleNode(ListNode head) {
        List<ListNode> arr = new List<ListNode>();
        ListNode cur = head;
        while (cur != null) {
            arr.Add(cur);
            cur = cur.next;
        }
        return arr[arr.Count / 2];
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    arr := []*ListNode{}
    cur := head
    for cur != nil {
        arr = append(arr, cur)
        cur = cur.Next
    }
    return arr[len(arr)/2]
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        val arr = mutableListOf<ListNode>()
        var cur = head
        while (cur != null) {
            arr.add(cur)
            cur = cur.next
        }
        return arr[arr.size / 2]
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var arr = [ListNode]()
        var cur = head
        while cur != nil {
            arr.append(cur!)
            cur = cur?.next
        }
        return arr[arr.count / 2]
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut arr = Vec::new();
        let mut cur = &head;
        while let Some(node) = cur {
            arr.push(node.clone());
            cur = &node.next;
        }
        let mid = arr.len() / 2;
        Some(arr.remove(mid))
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Find Length of the List

Intuition

We can avoid storing all nodes by first counting the total number of nodes, then making a second pass to reach the middle. This uses constant extra space since we only store the count and a pointer.

Algorithm

Traverse the list once to count the total number of nodes n.
Calculate the middle position as n / 2.
Traverse the list again, moving forward n / 2 steps from the head.
Return the node at that position.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        n, cur = 0, head
        while cur:
            cur = cur.next
            n += 1

        n //= 2
        cur = head
        while n:
            n -= 1
            cur = cur.next
        return cur

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            n++;
        }

        n /= 2;
        cur = head;
        while (n != 0) {
            n--;
            cur = cur.next;
        }
        return cur;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int n = 0;
        ListNode* cur = head;
        while (cur) {
            cur = cur->next;
            n++;
        }

        n /= 2;
        cur = head;
        while (n) {
            n--;
            cur = cur->next;
        }
        return cur;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    middleNode(head) {
        let n = 0;
        let cur = head;
        while (cur) {
            cur = cur.next;
            n++;
        }

        n = Math.floor(n / 2);
        cur = head;
        while (n) {
            n--;
            cur = cur.next;
        }
        return cur;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MiddleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            n++;
        }

        n /= 2;
        cur = head;
        while (n > 0) {
            cur = cur.next;
            n--;
        }

        return cur;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    n := 0
    cur := head
    for cur != nil {
        cur = cur.Next
        n++
    }

    n /= 2
    cur = head
    for n > 0 {
        n--
        cur = cur.Next
    }
    return cur
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        var n = 0
        var cur = head
        while (cur != null) {
            cur = cur.next
            n++
        }

        n /= 2
        cur = head
        while (n > 0) {
            n--
            cur = cur?.next
        }
        return cur
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var n = 0
        var cur = head
        while cur != nil {
            cur = cur?.next
            n += 1
        }

        n /= 2
        cur = head
        while n > 0 {
            n -= 1
            cur = cur?.next
        }
        return cur
    }
}

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut n = 0;
        let mut cur = &head;
        while let Some(node) = cur {
            cur = &node.next;
            n += 1;
        }

        n /= 2;
        let mut cur = head;
        for _ in 0..n {
            cur = cur.unwrap().next;
        }
        cur
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

3. Fast & Slow Pointers

Intuition

The fast and slow pointer technique finds the middle in a single pass. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle. This works because the fast pointer covers twice the distance in the same number of iterations.

Algorithm

Initialize both slow and fast pointers at the head.
While fast is not null and fast.next is not null:
- Move slow one step forward.
- Move fast two steps forward.
Return slow, which now points to the middle node.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    middleNode(head) {
        let slow = head,
            fast = head;

        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MiddleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        var slow = head
        var fast = head
        while (fast != null && fast.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }
        return slow
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
}

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut n = 0;
        let mut cur = &head;
        while let Some(node) = cur {
            n += 1;
            cur = &node.next;
        }
        let mid = n / 2;
        let mut cur = head;
        for _ in 0..mid {
            cur = cur.unwrap().next;
        }
        cur
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Incorrect Loop Condition for Fast Pointer

When using the fast and slow pointer technique, the loop condition must check both fast and fast.next before advancing. Checking only fast can cause a null pointer exception when trying to access fast.next.next. The correct condition is while (fast != null && fast.next != null).

Off-by-One Error with Even-Length Lists

For lists with an even number of nodes, there are two middle nodes. The problem typically asks for the second middle node, but some implementations accidentally return the first. Ensure your pointer movement logic returns the correct middle based on the problem requirements.