Bdtjtk

I am trying to write a code to remove duplicates from a sorted linked list "head". My code below always returns the last duplicate if the list ends with a duplicate. for e.g. [1,2,2,3,3] will return [1,2,3,3]. I can't figure out why. Does anyone have an idea?

class Solution(object):

    def deleteDuplicates(self, head):

        """

        :type head: ListNode

        :rtype: ListNode

        """



        if not head:

            return head



        l1=newhead=ListNode(head.val)

        head=head.next





        while head:

            if head.val!=l1.val:

                l1.next=head

                l1=l1.next

            head=head.next



        return newhead

You should keep track of the leading node of each new value and keep fetching the next node until you get a node with a different value, at which point you assign that node as the next node for the leading node:

class Solution(object):

    def deleteDuplicates(self, head):

        node = head

        while node:

            lead = node

            while node.next and node.next.val == lead.val:

                node = node.next

            node = lead.next = node.next

        return head

Problem Solution

1. Create a class Node with instance variables data and next.


2. Create a class LinkedList with instance variables head and last_node.


3. The variable head points to the first element in the linked list while last_node points to the last.


4. Define methods append, get_prev_node, remove and display.


5. The method append takes a data item as argument and appends a node with that data item to the list.


6. The method get_prev_node takes a reference node as argument and returns the previous node. It returns None when the reference node is the first node.


7. The method remove takes a node as argument and removes it from the list.


8. The method display traverses the list from the first node and prints the data of each node.


9. Define a function remove_duplicates which takes a linked list as argument and removes duplicates from it.


10. The function remove_duplicates uses two nested loops to remove duplicate nodes.


11. Create an instance of LinkedList, remove duplicate nodes and display the list.

Program/Source Code

Here is the source code of a Python program to remove duplicates from a linked list.

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None





class LinkedList:

    def __init__(self):

        self.head = None

        self.last_node = None



    def append(self, data):

        if self.last_node is None:

            self.head = Node(data)

            self.last_node = self.head

        else:

            self.last_node.next = Node(data)

            self.last_node = self.last_node.next



    def get_prev_node(self, ref_node):

        current = self.head

        while (current and current.next != ref_node):

            current = current.next

        return current



    def remove(self, node):

        prev_node = self.get_prev_node(node)

        if prev_node is None:

            self.head = self.head.next

        else:

            prev_node.next = node.next



    def display(self):

        current = self.head

        while current:

            print(current.data, end = ' ')

            current = current.next





def remove_duplicates(llist):

    current1 = llist.head

    while current1:

        data = current1.data

        current2 = current1.next

        while current2:

            if current2.data == data:

                llist.remove(current2)

            current2 = current2.next

        current1 = current1.next





a_llist = LinkedList()



data_list = input('Please enter the elements in the linked list: ').split()

for data in data_list:

    a_llist.append(int(data))



remove_duplicates(a_llist)



print('The list with duplicates removed: ')

a_llist.display()

Program Explanation

1. An instance of LinkedList is created.


2. The user is prompted to enter the data items for the list.


3. The function remove_duplicates is called to remove duplicates from the list.


4. The linked list is displayed.