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

# 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

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.

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.