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
```

- Initialize
`current`

to point to the first node, which contains the value 1. - Initialize
`runner`

to point to the same node as`current`

. - Iterate through the rest of the linked list using
`runner`

. The first node we encounter is the node with the value 2. - 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`

. - 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. - We move on to the next node by updating
`current`

to point to the node with the value 2. - Initialize
`runner`

to point to the same node as`current`

. - 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. - The next node we encounter is the node with the value 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 -> None`

. - 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. - Initialize
`runner`

to point to the same node as`current`

. - 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).