83. Remove Duplicates from Sorted List

Published on July 10, 2023

Question

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.

Algorithm

The solution to this problem is strait forward. Actually all the Linkedlist questions is like this, you figure out the relationship or the operation for single node or single pair of node(prev and cur), you can apply them in the whole list by looping.

Here we are asked to remove duplicates and we could find that, we can keep the pre position when its next's value is equal to its value, and loop until the next value is not equal to the previous one's. Then connect the previous one with the new cur, so we remove all the duplicates value ones in the middle.

Code

/**
 * 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) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode prev = head;
        ListNode cur = head.next;
        
        while (cur != null) {
            if (prev.val == cur.val) {
                while (cur != null && prev.val == cur.val) {
                    cur = cur.next;
                }
                prev.next = cur;
            } 
            if (cur == null) break;
            cur = cur.next;
            prev = prev.next;
        
        }
        return head;
    }
}