Search in a sorted multi-level linked list

Given a multi-level linked list as shown in this post. Write code to search in such a list.

The structure of the list is as shown below:

The important thing is that each of the child lists is sorted and all the elements in the child list of a node are less than the next node in the top list.
If we are searching for 3, then that value cannot be found after the Node 5 in the main list. So, we can stop the search when a value greater than what we are searching for is encountered. To understand it better, let us see the code of searching in a normal list

bool search(Node* h, int x)
{
  while(h != NULL)
  {
    if(h->data == x)
      return true;
  }
  return false;
}

and compare it with the code to search in a sorted linked list

bool search(Node* h, int x)
{
  while(h != NULL && h->data<=x)
  {
    if(h->data == x)
      return true;
  }
  return false;
}

Note the condition in the while loop. If the list is sorted, then we can stop when a value greater than x is found in the list (because x cannot be present after that). But if the list is not sorted, then we have to traverse the entire list.
We can use the same logic here because both the top list and the child lists are sorted. Below is the code that searches for a value in the given list arrangement.

bool search(Node* h, int x)
{
  while(h != NULL)
  {
    if(h->data == x)
      return true;
    ChildNode *temp = h->down;
    while(temp != NULL)
    {
      if(temp->data == x)
        return true;
      temp = temp->next;
    }
    h = h->next;
  }
  return false;
}

The time taken by the above code is O(n), where n is the total number of elements in the entire list.