Question

• in python
• Take advantage of the fact that the range of the integers in the list is fixed (0 to m, where m is the largest ID you can find in the linked list). Use a boolean array seen of length m+1 to indicate if elements in the array have been seen before. Then determine if there are duplicates by performing a single pass through the unsorted list. Hint: while traversing the list, seen[item] = True if integer item has been seen before in the search.
• 0
  1
  15
  112
  5000
• 150
  112
  5000

Answer 1

since you have not provided the code of the linked list, I am assuming that the linked list is represented using the node defintion:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

CODE

def duplicates(lst, m):

seen = [False for i in range(0, m + 1)]

temp = lst.head

while (temp):

if (seen[temp.data] is True):

print("This list has duplicates")

return

seen[temp.data] = True

print("This list does not have duplicates")

​​​​​​​