LeetCode #83 Remove Duplicates from Sorted List Solution & Explanation

LeetCode Problem

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.

Solution

The third point of constraints is important for solving this problem ➡ the list were sorted in ascending order.

The first solution  occurred to me is to use iteration to check the next number is same or not, if same than skip it, if not than add it to a new linked list.

C# Solution

Solution1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        
        ListNode resNode = new ListNode();
        
        if(head == null){return head;}
        ListNode copyNode = resNode;

        copyNode.val = head.val;
        
        while(head!=null)
        {
            if(copyNode.val!=head.val)
            {
                ListNode newNode = new ListNode();
                newNode.val = head.val;
                
                copyNode.next = newNode;
                copyNode = newNode;
            }
            
            head = head.next;
        }
            
        return resNode;
    }
}

Solution2

In our second solution, we get the value of the whole linked list, and save them into a int list.

Then, we use LINQ to distinct the list and remake a new linked list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode resNode = new ListNode();
        List<int>valList = new List<int>();

        //1.get val list distinct first
        if(head == null){return head;}
        while(head != null)
        {
            valList.Add(head.val);
            head = head.next;
        }
        valList = valList.Distinct().OrderBy(x => x).ToList();
        
        
        //2.remake a linked list and return
        resNode.val = valList[0];
        ListNode lastNode = resNode;
        
        for(int i =1;i<valList.Count;i++)
        {
            ListNode nowNode = new ListNode();
            nowNode.val = valList[i];
            lastNode.next = nowNode;
            lastNode = nowNode;
        }

        return resNode;
    }
}

Java Solution

Solution1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode resNode = new ListNode();
        
        if(head == null){return head;}
        ListNode copyNode = resNode;

        copyNode.val = head.val;
        
        while(head!=null)
        {
            if(copyNode.val!=head.val)
            {
                ListNode newNode = new ListNode();
                newNode.val = head.val;
                
                copyNode.next = newNode;
                copyNode = newNode;
            }
            head = head.next;
        }
        return resNode; 
    }
}

Runtime : 1ms、0ms、1ms

Python3 Solution

Solution1

# 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]:
        resNode = ListNode()
        if(head == None):
            return head
        
        copyNode = resNode
        copyNode.val = head.val
        
        while(head!=None):
            if(copyNode.val!=head.val):
                newNode = ListNode()
                newNode.val = head.val
                
                copyNode.next = newNode
                copyNode = newNode
            head = head.next
        return resNode

Runtime : 44ms、55ms、51ms ≈ Faster than 80~95%

JavaScript Solution

Solution1

/**
 * 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}
 */
var deleteDuplicates = function(head) {
        var resNode = new ListNode();
        
        if(head == null){return head;}
        var copyNode = resNode;

        copyNode.val = head.val;
        
        while(head!=null)
        {
            if(copyNode.val!=head.val)
            {
                var newNode = new ListNode();
                newNode.val = head.val;
                
                copyNode.next = newNode;
                copyNode = newNode;
            }
            head = head.next;
        }
        return resNode; 
};

Conclusion

🧡If my solution helps, that is my honor!

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

The problem link : Remove Duplicates from Sorted List – LeetCode

Latest Post

• Codeforces 1760A Medium Number Solution & Explanation2024-04-24
• LeetCode #234 Palindrome Linked List Solution & Explanation2024-04-23
• LeetCode #168 Excel Sheet Column Title Solution & Explanation2024-04-22
• Codeforces 1791A Codeforces Checking Solution & Explanation2024-04-21
• Codeforces 1807A Plus or Minus Solution & Explanation2024-04-20