My Solution and A case that this OJ didn't check


  • -1
    A

    there is a case : [1 2 3 3 3 5 6 2 2 6 5 2 ]

    the result should be : [1]

    but most of the solution in the descuss run out the result : [1 2 5 6 6 5 2]

        // my solution:
    class Solution {
     public:
      ListNode* deleteDuplicates(ListNode* head) {
        stack<ListNode *> stk;
        bool flag = false; // true means the stk top need to be pop
        ListNode * cur = head;
        while (cur != NULL) {
          if (stk.empty()) {
            stk.push(cur);
            cur = cur->next;
            flag = false;
          } else if (cur->val == stk.top()->val) {
            flag = true;
            // because we don't know how the program frame manage the memory,
            // so i didn't free the  duplicate ListNode
            cur = cur->next;
            continue;
          } else if (flag) {
            stk.pop();
            flag = false;
          } else {   
            stk.push(cur);
            cur = cur->next;
          }   
        }   
        if (flag) stk.pop(); 
    
        // the remaining node in the stack is the result
        ListNode * res = NULL;
        while(!stk.empty()) {
          ListNode* t = stk.top();
          stk.pop();
          if (res == NULL) {
            res = t;
            res->next = NULL;
          } else {
            t->next = res;
            res = t;
          }
        }
        return res;
      }
    };

  • 0
    F

    Did you read the question? It says "sorted linked list".
    [1 2 3 3 3 5 6 2 2 6 5 2 ] is not sorted!


Log in to reply
 

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