Linked List into Graph

What is interesting about this problem is that despite the fact of the input be a Linked List, it is actually easier to solve the problem if you transform the Linked List into a Graph.

The idea being is that you want to find the connected components in the Linked List. By transforming it into a Graph, we can perform a DFS just marking the connected components, which makes the solution very simple and running in linear time. Since there is the drawback of parsing the list and creating the extra graph data structure (which as I mentioned before, I’m a big fan of a Hashtable(key, Hashtabls()) as my favorite graph data structure these days), it incurs some penalties in terms of execution time as well as space used, but still enough for a pass. Code is down below, cheers, ACC.

Linked List Components - LeetCode

You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.

Return the number of connected components in nums where two values are connected if they appear consecutively in the linked list.

 

Example 1:

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

 

Constraints:

• The number of nodes in the linked list is n.
• 1 <= n <= 104
• 0 <= Node.val < n
• All the values Node.val are unique.
• 1 <= nums.length <= n
• 0 <= nums[i] < n
• All the values of nums are unique.

public int NumComponents(ListNode head, int[] nums)
{
    Hashtable graph = new Hashtable();
    ListNode previous = null;
    for (ListNode t = head; t != null; t = t.next)
    {
        if (!graph.ContainsKey(t.val)) graph.Add(t.val, new Hashtable());
        Hashtable connections = (Hashtable)graph[t.val];
        if (previous != null && !connections.ContainsKey(previous.val)) connections.Add(previous.val, true);
        if (t.next != null && !connections.ContainsKey(t.next.val)) connections.Add(t.next.val, true);

        previous = t;
    }

    Hashtable validNode = new Hashtable();
    foreach (int n in nums) validNode.Add(n, true);

    int retVal = 0;
    Hashtable visited = new Hashtable();
    foreach (int n in nums)
    {
        if (!visited.ContainsKey(n))
        {
            DFSMark(n, graph, visited, validNode);
            retVal++;
        }
    }

    return retVal;
}

private void DFSMark(int currentNode,
                        Hashtable graph,
                        Hashtable visited,
                        Hashtable validNode)
{
    if (!validNode.ContainsKey(currentNode) || visited.ContainsKey(currentNode)) return;
    visited.Add(currentNode, true);

    if (graph.ContainsKey(currentNode))
    {
        Hashtable connections = (Hashtable)graph[currentNode];
        foreach (int node in connections.Keys)
        {
            DFSMark(node, graph, visited, validNode);
        }
    }
}