[Leetcode] 82. Remove Duplicates from Sorted List II

 

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Loading...

---

 

1. Problem 

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

Input: 1->2->3->3->4->4->5

Output: 1->2->5

 

2. Algorithm

Solving this problem, we can choose to making new list as return value or using given list. My choice was to make new one. 

 

Step 1. Initialize root node and temp node for a new list.  I added cnt and before value for counting duplicated number.  Value before will contains number value of before node. Intialize it with the value of head node and cnt as '0'.

 

Step 2. Search values of each node while head isn't null value. If the value is same with the before value, and then increase cnt. If not, we will make a node for new list with the value we have contained only when the cnt is '1'. (This means the number appeared just one time.) And then move temp to the next.

 

Step 3. After searched all nodes, check the last node is a distinct node. If the while loop ended with 'cnt == 1', and add node which contains before value to the new list. We should check the root is not null. If that is null, it means this is the first node of  a new list.

This is my O(n) solution.

 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        // Step 1
        ListNode root = null, temp = null; 
        int before = head.val, cnt = 0;
        // Step 2
        while(head != null) {	
            if (head.val == before) cnt++;
            else {
                if (cnt == 1) {
                    if (root == null) {
                        root = new ListNode(before);
                        temp = root;
                    } else {
                        temp.next = new ListNode(before);
                        temp = temp.next;
                    }
                }
                before = head.val;
                cnt = 1;
            }
            head = head.next;
        }
        // Step 3
        if (cnt == 1) {		
        	if (root == null) root = new ListNode(before);
        	else temp.next = new ListNode(before);
        }
        
        return root;

    }
}

 

Or we can use HashMap for searching duplicated nodes. Speed is much more slower, but this is more easy to understand in my opinion and still O(n) solution. (Technically, O(2n)) 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        HashMap<Integer, Boolean> map = new HashMap<>();
        ListNode temp = head, res = null;
                  
       
        while(temp != null) {
          map.put(temp.val, map.containsKey(temp.val)?false:true); // True means a distinct number.  
          temp = temp.next;
        }
        while(head != null) {
        	// Step 1. If the value is distinct, then add it to list.
            if(map.get(head.val)) { 
            	// Step 1-1.When the res is null, make head node for new list.
                if (res == null) {	
                    res = new ListNode(head.val);
                    temp = res;
                // Step 1-2. Or, just add next node.
                } else { 
                    temp.next = new ListNode(head.val);
                    temp = temp.next;
                }
            }	
            // Step 2. If not, just move to next node.
            head= head.next;
        }
        
        return res;

    }
}

 

 

 

3. retrospective

I took so long time to solve, because I didn't implement my first idea. Actually I wanted to use two pointers but there were many exceptional cases. So I changed my strategies many times but solved.

I'm not sure which solution is better way, but I found solution which is similar with my first idea. In this case, the writer used fakeHead to solve exceptional case problem, and I think this is briliant. Here is the solution.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        ListNode fakeHead = new ListNode(Integer.MIN_VALUE);
        fakeHead.next = head;
        ListNode slow = fakeHead, fast = fakeHead.next;
        
        while(fast != null) {
            while(fast.next != null && fast.val == fast.next.val) fast = fast.next;
            if(slow.next == fast) slow = slow.next;
            else slow.next = fast.next;
            fast = fast.next;
        }
    
        return fakeHead.next;
    }
}

Actually the speed is similar with mine, but this code is easy to read and interesting strategy.