My C++ solution with O(n) and space O(1), and any simpler code?


  • -1
    V

    the function that delete one duplicates node string.

    ListNode *deleteAllSameNodes(ListNode *node) {
        int to_deleted_value = node->val;
        ListNode *walker = node;
    
        while (walker != 0 && walker->val == to_deleted_value)    
        {
        ListNode *tmp = walker;
        walker = walker->next;
            delete tmp;
    }
    
        return walker;
    }
    

    I go through the node and set two pointer to pick the duplicate ones
    just like what I do in problem "Remove Duplicates from Sorted Array"

    class Solution {
    public:
    ListNode *deleteDuplicates(ListNode *head) {
    	if (head == 0) return head;
    
    	ListNode *current = head;
        ListNode *walker = current->next;
    
    	// O(n)
    	// tmp is used for temp storage of the formal ListNode
    	for (ListNode *tmp = 0; walker != 0 && current != 0; walker = walker->next)
    	{
    		if (current->val != walker->val)
    		{
    			tmp = current;
    			current = current->next;
    			continue;
    		}
    		else
    		{
    			if (tmp == 0)
    			{
    				walker = current = head = deleteAllSameNodes(current);
    			}
    			else
    			{
    				walker = current = tmp->next = deleteAllSameNodes(current);
    			}
    			
    			if (walker == 0) break;
    		}
    	}
    
    	return head;
    }
    };

  • 0

    O(n^2) time.


  • 0
    N

    this is not O(n) ! Miss leading.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.