Member Avatar for Q8iEnG

Hi my friends, how do you do?

I hope everything is alright.. :)


Please may I have a few mins. from your time? It'll be much more appreciated :)

I have this question
(Write a member function to check whether two singly linked lists have the same contents.)


anyone can help me solving this question, plz?


thanks in advance... Be sure, I'll be thankful if I get a few mins. from your time to solve this question :)..

  • 4 Contributors
  • 9 Replies
  • 178 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Q8iEnG

Dani AI

Generated

Short answer: walk two pointers through the lists in parallel, compare each node’s value, advance both pointers, and at the end both pointers must be null. The algorithm is O(n) time and O(1) extra space.

A simple member function (as an example) that implements this idea:

bool List::sameContents(const List& other) const {
    Node* p = head;
    Node* q = other.head;
    while (p != nullptr && q != nullptr) {
        if (!(p->data == q->data))    // relies on operator== for the stored type
            return false;
        p = p->next;
        q = q->next;
    }
    return p == nullptr && q == nullptr; // both must finish at the same time
}

Notes and pitfalls:

  • had the right approach; the important step that can be missed is advancing both pointers inside the loop. Without advancing you never make progress.
  • If Node::data is a pointer or a custom type, decide whether you want pointer-equality or value-equality and make sure operator== does the right thing (or pass a comparator).
  • For floating-point values compare with a tolerance rather than exact equality.
  • If lists might contain cycles, run cycle detection first (Floyd’s fast/slow). Comparing naive pointers on cyclic lists can loop forever or give wrong results.
  • If “same contents” should ignore order (multiset equality) that requires a different approach (hash/count or sort), not the linear pairwise scan.

Quick troubleshooting checklist: test two empty lists, lists of different lengths, identical lists, lists that differ at the first/last/middle element, and cases with duplicate values. This will expose common implementation bugs.

Recommended Answers

All 9 Replies

Member Avatar for Member #46692

What ideas do you have?

Read the rules about homework, we only help if effort is shown by you.

Member Avatar for Q8iEnG

About the rules Yes, I know them

But this is not from my personality to lie at ppl :\

I'll tell the truth that really I don't know anything about the linked lists :\

if I give it a try

I would say (this code below)

void checkEquality()
{
for( int i = 0; i < 
}

then I get stuck there..

Please, Absolutely this is my 1st time asking for something without doing a big work :\

I'm really getting stuck in that step

also, it is not a homework

I'm studying for my midterm and trying to solve the problem sets in the book

Thanks in advance.. waiting your help :)

Member Avatar for Q8iEnG

Thanks a lot Narue you saved me in some questions I was getting stuck with them xDD

but for my question I didn't figure how to implement the code for TWO singly linked lists :'[

It looks confusing because for one for loop I can take one singly linked list,, and for two!! How I can do it???

Please, it is a function not a program!!

or at least tell me and I'll implement it :)

Member Avatar for Narue

>but for my question I didn't figure how to implement the code for TWO singly linked lists :'[
Dude, it's just like using two arrays. Please don't tell me you're as dense as that statement suggests.

Member Avatar for Q8iEnG

so you meant, I'll use the code as they're two arrays!!

Member Avatar for Narue

I meant, you can have more than one linked list:

node *it1 = head1;
node *it2 = head2;

while ( it1 != 0 && it2 != 0 ) {
  if ( it1->data != it2->data )
    break;
}

if ( it1 == 0 && it2 == 0 )
  cout<<"Equal";
commented: You saved me :D +1
Member Avatar for CoolGamer48

Do you know about ? You could create a Linked List template class to make things easier to understand. Though, on second thought, creating a linked list template class can be a hassle, and giving you one wouldn't teach you anything about linked lists.

Member Avatar for Q8iEnG

Narue,, thank you so much.. it did came in the midterm and I solve it in the way you said xDD

thank you so much,, (Added Rep for you) :)

++++++++

CoolGamer

I don't think it needs the Template because the question want only the member function so no need for the other details ;)


thanks again guys :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.