2022-02-01-112425-876_middle_of_the_linked_list.org

876. Middle of the Linked List

Description

Given the head of a singly linked list, return the middle node of the linked list.

Constraints:

1. The number of nodes in the list is in the range [1, 100].
2. $1 \leq Node.val \leq 100$

Examples:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Solution

Understanding the problem

Trivial case is a single node. We should just return the node.

Bottom line is we have to traverse all nodes before we know which one is the middle one. So time complexity has to be at least O(N).

Naively we can put all nodes in a list as we scan the linked list and get the middle node. That would cost O(N) space. However, we can use some math and only record the mid node mid_node when our scanning pointer pos position changes.

Algorithm

1. Initialise mid_node = head, pos = 0, curr_node = head
2. while curr_node.next is not None
   1. curr_node = curr_node.next
   2. pos += 1
   3. if pos % 2 == 1, mid_node = mid_node.next

Code

def middleNode(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    mid_node = head
    pos = 0
    curr_node = head
    while curr_node.next:
        curr_node = curr_node.next
        pos += 1
        if pos % 2 == 1:
            mid_node = mid_node.next

    return mid_node

Complexity

Time complexity:

O(N)

Space complexity:

O(1)

Leetcode solution

nil.

<<imports for typing>>

Time complexity:

Space complexity:

More analysis

General thoughts

Related problems

Log time