# Contiguous blocks in linked list

• Given a list of linkedlist nodes and the linked list, find the number of contiguous blocks.
Ex:
list: [a,c,b,e]
linked list: a -> b -> c -> d -> e

Output: 2

Answer: Linked list is a bit of a red herring. You can just go through the list and check if any of the next pointers point to anything else in the list.

• ``````int number_of_contiguous_blocks(unordered_set<node*> nodes, node* head)
{
unordered_map<node*, bool> seen;
int count = 0;
for(node* _node: nodes) {
seen.insert(make_pair(_node, false));
if(seen.find(_node->next) == seen.end()){
count++;
seen[_node]=true;
}
}
for(node* _node:nodes){
if( seen[_node] && seen.find(_node->next) != seen.end() )
count--;
}
return count;
}
``````

• An important observation is that any contiguous block of nodes must come to an end. That is, the last node in a contiguous block will point to a node that does not exist in the list of nodes. We can then come up with a pretty clean solution:

``````int numContiguousBlocks(vector<Node*> nodes) {
unordered_set<Node*> marked_nodes(nodes.begin(), nodes.end());
int count = 0;
for (Node* n : nodes) if (!marked_nodes.count(n->next)) ++count;
return count;
}
``````

Like the OP said, a pointer to the head of the linked list is not needed. We only need the list of nodes to solve the problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.