# Questions

### Remove redundancy in a linked list

0

We define a redundant node in a singly-linked list to be a node whose value matches the value of a previous node in the list. In
other words, an earlier value recurs.

For example, consider the following linked list with one
redundant node: A zero-indexed list in the form list = [3, 4, 3, 6] with a redundant node at index 2.

You will be given a singly-linked list that may contain redundant nodes. You must create a singly-
linked list containing only unique values as they first occur in the inputs.

Sample Input 0
8
3
4
3
2
6
1
2
6

Sample Output 0
3
4
2
6
1

Explanation
The list head = 3 → 4 → 3 → 2 → 6 → 1 → 2 → 6 → null asked 1 year, 7 months ago
Reputation: 1

0

You can do this using a dictionary look up. At the time of visiting a node just check if you have visited that node earlier. If you have visited it earlier just delete it and proceed.

To do this you need to maintain the lookup hash table. You can use dictionary for that.

Here is the distinct function.

distinct() function

``````def distinct(self):
if(not prev):
return

dict={}
dict[prev.data] = 1
temp = prev.next

while(temp):
if(temp.data in dict):
temp1 = temp
prev.next = temp.next
temp = temp.next
temp1 = None
else:
prev = temp
temp = temp.next
dict[prev.data] = 1
``````

Complexity

Time: O(N)
Space: O(N)

Complete Program

``````class Node(object):
"""docstring for Node."""
def __init__(self, data):
super(Node, self).__init__()
self.data = data
self.next = None

def __init__(self):

def append(self, new_data):
new_node = Node(new_data)

return

while(last.next):
last = last.next

last.next = new_node

def print_list(self):
while(temp):
print(temp.data, end="")
print("---->", end="")
temp = temp.next
print("NULL")

def distinct(self):
if(not prev):
return

dict={}
dict[prev.data] = 1
temp = prev.next

while(temp):
if(temp.data in dict):
temp1 = temp
prev.next = temp.next
temp = temp.next
temp1 = None
else:
prev = temp
temp = temp.next
dict[prev.data] = 1

# Now taking user input and giving output
inp_list = list(map(int, input().split()))

for ele in inp_list:
sll.append(ele)

sll.print_list()

sll.distinct()
sll.print_list()
``````

Output Screenshot  answered 1 year, 7 months ago
Reputation: 1