Naive Solution

The most straightforward approach is to iterate through the linked list, identify critical points, store their indices, and then calculate the minimum and maximum distances between these critical points. This involves a linear scan to find the critical points and then a nested loop to compare the distances between all pairs of critical points.

Code (Python):

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

def critical_points(head):
    if not head or not head.next:
        return [-1, -1]

    nodes = []
    while head:
      nodes.append(head.val)
      head = head.next

    n = len(nodes)
    critical_pts = []
    for i in range(1, n - 1):
        if nodes[i] > nodes[i - 1] and nodes[i] > nodes[i + 1]:
            critical_pts.append(i + 1)
        elif nodes[i] < nodes[i - 1] and nodes[i] < nodes[i + 1]:
            critical_pts.append(i + 1)

    if len(critical_pts) < 2:
        return [-1, -1]

    min_dist = float('inf')
    max_dist = 0

    for i in range(len(critical_pts)):
        for j in range(i + 1, len(critical_pts)):
            dist = critical_pts[j] - critical_pts[i]
            min_dist = min(min_dist, dist)
            max_dist = max(max_dist, dist)

    return [min_dist, max_dist]

Time Complexity: O(N^2), where N is the number of nodes in the linked list. This is because we have a nested loop to calculate the distances between all pairs of critical points.

Space Complexity: O(N), where N is the number of nodes in the linked list. This is used to store the values of all the nodes and the critical point indices.

Optimal Solution

A more efficient approach involves iterating through the linked list only once. During this iteration, we identify critical points and simultaneously keep track of the minimum and maximum distances between them. This eliminates the need for nested loops.

Algorithm:

1. Initialize first_critical_point and last_critical_point to -1. These will store the index of the first and last critical points encountered.
2. Initialize min_distance to infinity and max_distance to 0.
3. Iterate through the linked list, starting from the second node.
4. For each node, check if it's a critical point.
5. If it's the first critical point encountered, update first_critical_point and last_critical_point.
6. If it's not the first critical point, calculate the distance between the current critical point and the previous one (last_critical_point). Update min_distance and max_distance accordingly. Then, update last_critical_point to the current critical point.
7. After the iteration, if fewer than two critical points were found, return [-1, -1]. Otherwise, return [min_distance, max_distance].

Code (Python):

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

def critical_points(head):
    if not head or not head.next or not head.next.next:
        return [-1, -1]

    first_critical_point = -1
    last_critical_point = -1
    min_distance = float('inf')
    max_distance = 0
    index = 1
    prev = head
    curr = head.next

    while curr.next:
        next_node = curr.next
        if curr.val > prev.val and curr.val > next_node.val:
            # Local maxima
            if first_critical_point == -1:
                first_critical_point = index + 1
                last_critical_point = index + 1
            else:
                min_distance = min(min_distance, (index + 1) - last_critical_point)
                max_distance = (index + 1) - first_critical_point
                last_critical_point = index + 1
        elif curr.val < prev.val and curr.val < next_node.val:
            # Local minima
            if first_critical_point == -1:
                first_critical_point = index + 1
                last_critical_point = index + 1
            else:
                min_distance = min(min_distance, (index + 1) - last_critical_point)
                max_distance = (index + 1) - first_critical_point
                last_critical_point = index + 1

        prev = curr
        curr = next_node
        index += 1

    if first_critical_point == last_critical_point:
        return [-1, -1]

    return [min_distance, max_distance]

Time Complexity: O(N), where N is the number of nodes in the linked list, as we iterate through the list only once.

Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases

• Empty list or list with only one node: Return [-1, -1] because there are no critical points.
• List with two nodes: Return [-1, -1] because a critical point requires a previous and next node.
• No critical points: Return [-1, -1] if no local minima or maxima are found.
• Only one critical point: Return [-1, -1] because we need at least two critical points to calculate distances.
• Critical points are adjacent: Ensure the minimum distance calculation correctly handles this scenario.