CODEWITHSUNDEEP
comparisonlinked-list
user370741
user370741

Reputation: 11

How to get the uncommon elements of two linked list?

Given two linked lists of integers. I was asked to return a linked list which contains the non-common elements. I know how to do it in O(n^2), any way to do it in O(n)?

Upvotes: 1

Views: 521

Answers (3)

Prateek
Prateek

Reputation: 71

create a new empty list. have a hash table and populate it with elements of both lists. complexity n. then iterate over each list sequentially and while iterating, put those elements in the new list which are not present in the hash table. complexity n. overall complexity=n

Upvotes: 1

Jamie Wong
Jamie Wong

Reputation: 18350

Use a hash table.

Iterate through the first linked list, entering the values you come across into a hash table.

Iterate through the second linked list, adding any element not found into the hash table into your list of non-common elements.

This solution should be O(n), assuming no collisions in the hash table.

Upvotes: 3

rmeador
rmeador

Reputation: 25694

If they're unsorted, then I don't believe it is possible to get better than O(n^2). However, you can do better by sorting them... you can sort in reasonably fast time, and then get something like O(nlogn) (I'm not certain that's what it would be, but I think it can be that fast if you use the right algorithm).

Upvotes: 0

Related Questions