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:

redundant_list.png

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, 5 months ago
Reputation: 1





1 Answer

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):
        prev = self.head
        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


class LinkedList(object):
    """docstring for LinkedList."""
    def __init__(self):
        super(LinkedList, self).__init__()
        self.head = None

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

        if self.head is None:
            self.head = new_node
            return

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

        last.next = new_node


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


    def distinct(self):
        prev = self.head
        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()))

sll = LinkedList()

for ele in inp_list:
    sll.append(ele)

print("Linked list before rmoving duplicates")
sll.print_list()

print("Linked list before rmoving duplicates")
sll.distinct()
sll.print_list()

Output Screenshot

output.png

answered 1 year, 5 months ago
Reputation: 1





Your Answer

Nothing to preview

Post Answer



Asked:  1 year, 5 months ago
Viewed:  858 times
Active:  1 year, 5 months ago