Problem 2: Remove Duplicates from Sorted List (easy)

Problem Statement:

Given a sorted linked list, remove all the duplicate elements to leave only distinct numbers. The linked list should remain sorted, and the modified list should be returned.

Examples

Example 1:

Input: 1 -> 1 -> 2
Output: 1 -> 2
Justification: Since 1 is repeated, we remove the duplicate to leave a sorted list of unique numbers.

Example 2:

Input: 1 -> 2 -> 2 -> 3
Output: 1 -> 2 -> 3
Justification: Here, 2 is the duplicate element, and by removing it, we obtain a list containing only distinct elements.

.....

Like the course? Get enrolled and start learning!

senthil kumar

· 2 years ago

Kindly add the main method and print method to avoid confusion and add clarity.

public void printList(ListNode head) {
    ListNode current = head;
    while (current != null) {
        System.out.print(current.val + " ");
        current = current.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // Test Example 1
    ListNode head1 = new ListNode(1, new ListNode(1, new ListNode(2)));
    ListNode result1 = solution.deleteDuplicates(head1); // Expected: 1 -> 2
    solution.printList(result1);

    // Test Example 2
    ListNode head2 = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(3))));
    ListNode result2 = solution

Daven L

· 2 years ago

class Solution:
    def deleteDuplicates(self, head):
        # so I dont lose my original head, I set a variable current
        current = head
        # traverse through LL, ensuring curr and curr.next exist
        while current and current.next is not None:
            # prev becomes the value to which we compare other values to
            prev = current
            current = current.next
            # we move current until current.val no longer matches prev value
            # ensure we don't hit None by checking that current also exists
            while current and prev.val == current.val:
                current = current.next
            # whether current is now None or some number that is not prev.val, we set prev.next
            prev.next = current
        return

Divyanshu Varma

· a year ago

/*
 * We should delete unused bypassed nodes otherwise
 * if you had n nodes to begin with and deleted m nodes 
 * you will still be consuming n nodes worth of memory. 
 */
 
ListNode* deleteDuplicates(ListNode* head) {
        if(!head or !head->next) { // base case
            return head;
        }

        auto curr = head, ahead = head->next; // adjacent nodes
        while(ahead) {
            if(curr->val == ahead->val) {
                auto temp = ahead;
                curr->next = ahead->next; // skip duplicate
                ahead = ahead->next;
                delete temp; // delete unused node
            } else {
                curr = curr->next;
                ahead = ahead->next;
            }
        }

        return head;
    }