algoadvance

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Clarifying Questions

1. Can the input linked list be empty?
   • Yes, the input can be an empty linked list.
2. Is the linked list sorted in non-decreasing order?
   • Yes, the linked list is sorted in non-decreasing order.
3. Can we modify the existing linked list or do we need to create a new one?
   • You can modify the existing linked list.

Strategy

1. Initialize a Pointer:
   • Create a pointer current that starts at the head of the linked list.
2. Iterate Through the List:
   • Traverse the linked list using the current pointer.
   • For each node, check if it has a duplicate by comparing current.val with current.next.val.
3. Remove Duplicates:
   • If a duplicate is found (i.e., current.val == current.next.val), skip the next node by setting current.next to current.next.next.
   • If no duplicate is found, simply move current to the next node.
4. Termination:
   • Continue this process until the end of the linked list is reached.
5. Return the Modified List:
   • Return the head of the modified linked list.

Code

Here’s the implementation in Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    current = head
    
    while current and current.next:
        if current.val == current.next.val:
            # Skip the next node, it's a duplicate
            current.next = current.next.next
        else:
            # Move to the next node
            current = current.next
    
    return head

Explanation

• Initialization: A pointer current begins at the head of the linked list.
• Traversal: The while loop continues as long as current and current.next are not None.
  • If the value of the current node is equal to the value of the next node (current.next.val), then we skip the next node by adjusting the next pointer of the current node (current.next = current.next.next).
  • If the values are different, we move the current pointer to the next node (current = current.next).
• Return: After traversing the entire list and removing duplicates, the modified list is returned.

Time Complexity

• Time Complexity: O(n)
  • We only make a single pass through the linked list, hence the time complexity is linear in relation to the number of nodes, n.
• Space Complexity: O(1)
  • No extra space is used other than a few pointers, so the space complexity is constant.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?