BFS on linked list

Question

Implement a breadth-first search (BFS) algorithm to traverse a linked list, where each node contains a reference to the next node. Given the head of the linked list, return a list of values in the order they are visited during the BFS traversal. Ensure that your solution handles edge cases, such as an empty list.

Codemia · Accepted Answer

The problem requires us to perform a breadth-first search (BFS) traversal on a linked list. Although BFS is typically associated with tree or graph structures, in this case, we can apply it since we treat the linked list as a linear graph where each node points to the next. The BFS pattern is suitable here because we want to explore nodes level by level (or, in this case, node by node in the order they are linked).

1. **Initiate**: Start with the head of the linked list. If the head is `None`, return an empty list to handle the edge case of an empty list.  
2. **Create a Queue**: Use a queue to facilitate the BFS traversal. The queue will help us keep track of the nodes as we visit them.  
3. **Traversal**:  
   - Enqueue the head node.  
   - While the queue is not empty, do the following:  
     - Dequeue the front node and save its value.  
     - If the current node has a next node, enqueue that next node.  
4. **Return Values**: Once all nodes are processed, return the list containing the values collected during traversal.  
**Example**: For a linked list with nodes containing values 1 -> 2 -> 3 -> None, the traversal would yield [1, 2, 3].

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

class Solution:
    def bfs_linked_list(self, head):
        if not head:
            return []  # Handle edge case of empty list

queue = [head]  # Start with the head node
        result = []

while queue:
            current_node = queue.pop(0)  # Dequeue the front node
            result.append(current_node.value)  # Collect the value
            if current_node.next:
                queue.append(current_node.next)  # Enqueue the next node

return result  # Return the collected values
```

The time complexity of this BFS traversal is O(n), where n is the number of nodes in the linked list, because we visit each node exactly once. The space complexity is also O(n) in the worst case, as we may need to store all nodes in the queue if the linked list is very long. This is efficient given the constraints of the problem, as we need to visit each node to collect its value.

- **Empty List**: If the head is `None`, the function should return an empty list.  
- **Single Node**: If the linked list has only one node (e.g., head points to a node with value 1 and next is `None`), the result should be [1].  
- **Long Linked List**: Ensure that the function handles a long linked list effectively without exceeding memory limits.

BFS on linked list

ServiceNow

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

ServiceNow 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