CODEWITHSUNDEEP
c++listsubset
Joshua
Joshua

Reputation: 305

How to find if a list is a subset of another list?

struct Node {
    int value;
    Node* next;
};

bool propSubset(Node* p, Node* q) {
    if(q == nullptr) return false;
    if(p == nullptr && q != nullptr) return true;
    if(p->value < q->value) return false;
    if(p->value > q->value) return propSubset(p, q->next);
    return propSubset(p->next, q->next);
}

p is a subset of q if

p and q are both sorted in ascending order.

This is all I got but it doesn't work for case like p = {2, 4}, q = {1, 2, 3, 4}
How can I improve this? Thanks

Upvotes: 0

Views: 568

Answers (2)

Aditya Mone
Aditya Mone

Reputation: 226

Iterative solution may be better. Given lists of arbitrary length you don't want to run the risk of running out of stack space.

Also the size factor comes into play since the non-intersecting elements in q can be randomly distributed.

You may want to restructure your code something like:

bool propSubset(Node* p, Node* q) {
  int len_q = length(q); // assuming you have length function.
  if (length(p) >= len_q) return false;

  for(int i=0; i < len_q && p != nullptr; ++i) {
    if (p->value == q->value) p = p->next;
    if (p->value < q->value) return false; // That particular value in p is not in q.
    q = q->next;
  }
  if (p == nullptr) return true;
  return false;
}

Upvotes: 1

Malketh
Malketh

Reputation: 101

You're assuming that q's element that is not in p is always at the very end of the list. You need to take into account that the extra element can be anywhere in the list and not just the end of the list and you'll be on the right path.

Upvotes: 0

Related Questions