Transform linked list to adjacency list

Question

Given a singly linked list where each node contains a value and a pointer to the next node, transform this linked list into an adjacency list representation of a graph. Each node's value should represent a vertex, and the adjacency list should reflect the connections between these vertices based on the linked list structure. The output should be a list of lists, where each inner list contains the neighbors of the corresponding vertex.

Codemia · Accepted Answer

The problem requires transforming a singly linked list into an adjacency list representation of a graph. Each node in the linked list corresponds to a vertex in the graph, while the next pointer of each node defines the connection (or edge) between vertices. This can be recognized as a graph traversal problem, where each node (vertex) connects to its successor. The adjacency list representation is an efficient way to store graph connections, especially given the linear structure of the linked list. Thus, we can utilize a simple traversal technique, iterating through the linked list to build the adjacency list.

1. Initialize an empty list `adjacency_list` to store the adjacency representation as a list of lists.
2. Create a pointer `current` that starts at the head of the linked list.
3. While `current` is not null:
   - Create a new list `neighbors` to represent the adjacency list for the vertex corresponding to `current`.
   - If `current.next` is not null, append the value of `current.next` to `neighbors` (indicating a connection to the next vertex).
   - Append `neighbors` to `adjacency_list`.
   - Move `current` to `current.next`.
4. Return `adjacency_list` at the end.

**Example:**
For a linked list: 1 -> 2 -> 3, the adjacency list will be:
- Vertex 1 connects to [2]
- Vertex 2 connects to [3]
- Vertex 3 connects to [] (no next node)
Thus, the output will be `[[2], [3], []]`.

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

def linked_list_to_adjacency_list(head):
    adjacency_list = []
    current = head
    while current:
        neighbors = []
        if current.next:
            neighbors.append(current.next.value)
        adjacency_list.append(neighbors)
        current = current.next
    return adjacency_list
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we traverse each node exactly once. The space complexity is also O(n) due to the storage of the adjacency list, which contains one sublist for each node in the linked list. This space is necessary to represent the graph structure.

1. **Empty List:** If the input linked list is empty (head is None), the output should be an empty list: `[]`.
2. **Single Node:** If the linked list contains only one node, the output should be `[][]`, as there are no neighbors for the single vertex.
3. **Multiple Nodes:** Ensure that the adjacency list correctly handles lists of varying lengths, including those where nodes may or may not have a next node (e.g., the last node should always show an empty list for its neighbors).

Transform linked list to adjacency list

Snapchat

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

Snapchat 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