We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Middle of the Linked List

Difficulty: Easy

Problem Description

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.

Key Insights

  • The middle of a linked list can be determined using the two-pointer technique (slow and fast pointers).
  • The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
  • When the fast pointer reaches the end of the list, the slow pointer will be at the middle.
  • If the list has an even number of nodes, the slow pointer will point to the second middle node.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To find the middle node of a singly linked list, we can use the two-pointer technique. We will maintain two pointers: slow and fast. The slow pointer will move one step at a time, while the fast pointer will move two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. This approach is efficient as it requires only a single traversal of the list, making it O(n) in time complexity. The space complexity is O(1) since we are using only a constant amount of space for the pointers.

Code Solutions

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

def middleNode(head: ListNode) -> ListNode:
    slow = head  # Initialize slow pointer
    fast = head  # Initialize fast pointer
    while fast and fast.next:  # Traverse the list
        slow = slow.next      # Move slow pointer one step
        fast = fast.next.next # Move fast pointer two steps
    return slow  # Slow pointer is at the middle node
← Back to All Questions