82. Remove Duplicates from Sorted List II

Problem

Tags: Linked List, Two Pointers

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Code

C

// 82. Remove Duplicates from Sorted List II (4/22/54155)
// Runtime: 7 ms (45.75%) Memory: 6.36 MB (61.64%) 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates (struct ListNode* head) {
    if (!head) {
        return head;
    }
    
    if (head->next && head->next->val == head->val) {
        while (head->next && head->next->val == head->val) {
            head = head->next;
        }
        return deleteDuplicates(head->next);
    }
    else {
        head->next = deleteDuplicates(head->next);
        return head;
    }
}

GO

// 82. Remove Duplicates from Sorted List II (4/29/54155)
// Runtime: 3 ms (74.19%) Memory: 3.05 MB (45.16%) 

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil;
    }
    
    if head.Next != nil && head.Next.Val == head.Val {
        for head.Next != nil && head.Next.Val == head.Val {
            head = head.Next;
        }
        return deleteDuplicates(head.Next);
    } else {
        head.Next = deleteDuplicates(head.Next);
        return head;
    }
}

JS

// 82. Remove Duplicates from Sorted List II (4/24/54155)
// Runtime: 95 ms (36.02%) Memory: 43.78 MB (92.66%) 

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function deleteDuplicates(head) {
    if (!head) {
        return head;
    }
    
    if (head.next && head.next.val === head.val) {
        while (head.next && head.next.val === head.val) {
            head = head.next;
        }
        return deleteDuplicates(head.next);
    } else {
        head.next = deleteDuplicates(head.next);
        return head;
    }
};

TS

// 82. Remove Duplicates from Sorted List II (4/25/54155)
// Runtime: 64 ms (92.39%) Memory: 45.42 MB (11.96%) 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (head === null) {
        return null;
    }
    
    if (head.next && head.next.val === head.val) {
        while (head.next && head.next.val === head.val) {
            head = head.next;
        }
        return deleteDuplicates(head.next);
    } else {
        head.next = deleteDuplicates(head.next);
        return head;
    }
};