Count maximum path in linked list

Question

Given a singly linked list, write a function to count the maximum number of nodes that can be visited in a path starting from any node and ending at any node, where each node can only be visited once. The function should return an integer representing the maximum path length. The input will be the head of the linked list, and the output will be the maximum count of nodes in a valid path.

Codemia · Accepted Answer

To solve the problem of counting the maximum path in a singly linked list, we should recognize that this is a traversal problem where we can treat the linked list as a graph. Each node points to the next node, and we need to find the longest simple path (where no node is revisited). This suggests a depth-first search (DFS) approach, as we can explore each possible path from every node and keep track of the maximum length found. Since each node can only be visited once in any single path, we need to ensure that our search does not revisit nodes.

1. Initialize a variable `max_length` to keep track of the maximum path length found.  
2. Implement a recursive DFS function that takes the current node and a set of visited nodes as parameters. This function will:  
   - Base case: If the current node is None, return the length of the path traveled so far.  
   - If the current node has been visited (exists in the set), return 0 as this path is invalid.  
   - Mark the current node as visited.  
   - Recursively call the DFS function for the next node in the linked list.  
   - Unmark the current node after the recursive call to allow for other paths.  
3. Iterate through each node in the linked list, calling the DFS function to explore paths starting from that node.  
4. Update `max_length` with the longest path returned from the DFS calls.

Here is the Python implementation of the algorithm:

```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def maxPathLength(head):
    def dfs(node, visited):
        if not node or node in visited:
            return 0
        visited.add(node)
        length = 1 + dfs(node.next, visited)
        visited.remove(node)
        return length

max_length = 0
    current = head
    while current:
        visited = set()
        max_length = max(max_length, dfs(current, visited))
        current = current.next

return max_length
```
This function defines a ListNode class for the linked list nodes and the `maxPathLength` function which implements the described DFS approach.

The time complexity of this solution is O(n^2) in the worst case, where n is the number of nodes in the linked list. This is due to the DFS potentially visiting each node for every starting node in the list. The space complexity is O(n) as well, primarily due to the recursive stack and the visited set storing up to n nodes in the worst case (for instance, if the linked list is a straight line).

1. **Empty List**: If the linked list is empty (head is None), the function should return 0 as there are no nodes to traverse.  
2. **Single Node**: If there is only one node in the list, the maximum path length should be 1.  
3. **Cyclic List**: The problem specifies that nodes can only be visited once, hence if the linked list has a cycle, our algorithm will correctly handle it by utilizing the visited set to avoid infinite loops.

Count maximum path in linked list

Elastic

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Elastic Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string