Remove duplicates from a linked list

Remove duplicates from a linked list in Python without extra space

To remove duplicates from a linked list in Python without using extra space, you can use a two-pointer approach where one pointer iterates through the list, and the other checks for duplicates and removes them.

Here’s an example implementation:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def remove_duplicates(head):
    current = head

    # iterate through the linked list
    while current is not None:
        # remove duplicates by iterating through the rest of the linked list
        runner = current
        while runner.next is not None:
            if runner.next.data == current.data:
                runner.next = runner.next.next
            else:
                runner = runner.next

        current = current.next

    return head

In this implementation, head is the head of the linked list. We first initialize the current pointer to the head of the linked list and iterate through the linked list.

For each node, we initialize another pointer called runner to the same node, and then we iterate through the rest of the linked list using runner. If we find a duplicate node, we remove it by updating the next pointer of runner to skip the duplicate node.

After removing all duplicates for the current node, we move on to the next node by updating current to current.next.

Finally, we return the head of the modified linked list.

The algorithm uses a two-pointer approach, where we use two pointers to traverse the linked list. The first pointer, called current, iterates through the list one node at a time. The second pointer, called runner, checks for duplicates and removes them.

For each node pointed to by current, we initialize runner to the same node. We then iterate through the rest of the linked list using runner and check if any of the nodes have the same data as the node pointed to by current. If we find a duplicate, we remove it by updating the next pointer of the previous node to skip the duplicate node.

After we have removed all duplicates for the node pointed to by current, we move on to the next node in the linked list by updating current to point to the next node.

Here is a step-by-step example of how the algorithm works on a linked list with duplicates:

1 -> 2 -> 2 -> 3 -> 4 -> 4 -> None

1. Initialize current to point to the first node, which contains the value 1.
2. Initialize runner to point to the same node as current.
3. Iterate through the rest of the linked list using runner. The first node we encounter is the node with the value 2.
4. Since the value of the node pointed to by runner is equal to the value of the node pointed to by current, we remove the duplicate node by updating the next pointer of the node pointed to by runner to skip the duplicate node. The linked list now looks like this: 1 -> 2 -> 3 -> 4 -> 4 -> None.
5. We continue iterating through the linked list using runner. The next node we encounter is the node with the value 3. Since there are no duplicates, we don’t do anything.
6. We move on to the next node by updating current to point to the node with the value 2.
7. Initialize runner to point to the same node as current.
8. Iterate through the rest of the linked list using runner. The first node we encounter is the node with the value 3. Since there are no duplicates, we don’t do anything.
9. The next node we encounter is the node with the value 4.
10. Since the value of the node pointed to by runner is equal to the value of the node pointed to by current, we remove the duplicate node by updating the next pointer of the node pointed to by runner to skip the duplicate node. The linked list now looks like this: 1 -> 2 -> 3 -> 4 -> None.
11. We continue iterating through the linked list using runner. Since we have reached the end of the linked list, we move on to the next node by updating current to point to the node with the value 3.
12. Initialize runner to point to the same node as current.
13. Since the node pointed to by runner is the last node in the linked list, we have reached the end of the algorithm.

The final linked list after removing duplicates is 1 -> 2 -> 3 -> 4 -> None.

Note that this implementation has a time complexity of O(n^2), where n is the length of the linked list, because we are iterating through the list for each node. If you need a more efficient solution, you can use a hash set to keep track of duplicates and remove them in a single pass with a time complexity of O(n).