Remove Duplicates from Sorted List

Problem Statement: 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.

Example 1
Input: head = [1,1,2]
Output: [1,2]
Example 2
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Constraints
  1. The number of nodes in the list is in the range [0, 300].
  2. -100 <= Node.val <= 100
  3. The list is guaranteed to be sorted in ascending order.

Solution

Approach

This method involves using two loops: one to traverse the string and another nested loop to identify various substrings. Afterwards, the process involves systematically checking each substring. For every element within these substrings, we verify if it’s not present; if not, we store it in a HashSet. Conversely, if the element is found, we break from the loop and tally the count.

 

Short Video Explanation

For a better understanding of the algorithm, please watch the video by clicking on the button below.

Code

Refer the code below for better understanding.

				
					# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:        
        curr=head
        while curr and curr.next:
            if curr.val ==curr.next.val:                
                curr.next=curr.next.next
            else:
                curr=curr.next
        return head
        
				
			
Time  and Space Complexity

Time Complexity: O(N)

Space Complexity: O(1) 

Explanation
  1. curr = head: This sets up a pointer curr to the head of the linked list.
  2. The while loop runs as long as curr exists and curr.next (the next node) exists. It checks each node and its next node in the list.
  3. if curr.val == curr.next.val: Compares the value of the current node with the value of its next node. If they’re the same, it means there’s a duplicate.
  4. If a duplicate is found (curr.val == curr.next.val), it bypasses the duplicate by adjusting the pointer. It makes curr.next point to the node after the next node, effectively skipping the duplicate node.
  5. If the values are different (else), it moves the curr pointer to the next node in the list for further comparison.
  6. Once the loop completes, it returns the modified linked list, starting from the original head.
WhatsApp
Facebook
Twitter
LinkedIn
Email

Leave a Reply

Your email address will not be published. Required fields are marked *

Welcome to our diverse learning options!

Select the learning format that suits your preferences and schedule.