Remove Duplicates from Unsorted List (ladder)

Description

Write code to remove duplicates from an unsorted linked list.

Example
Given 1->3->2->1->4.
Return 1->3->2->4

Challenge
(hard) How would you solve this problem if a temporary buffer is not allowed? In this case, you don't need to keep the order of nodes.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * Definition of ListNode
   * class ListNode {
   * public:
   *     int val;
   *     ListNode *next;
   *     ListNode(int val) {
   *         this->val = val;
   *         this->next = NULL;
   *     }
   * }
   */
   class Solution {
   public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    // // o(n) s(n)
     ListNode *removeDuplicates(ListNode *head) {
        // Write your code here
        if (!head) {
            return nullptr;
        }
        unordered_set<int> used;
        ListNode* cur = head;
        used.insert(cur->val);
        while (cur->next) {
            // cannot find
            if (used.find(cur->next->val) == used.end()) {
                used.insert(cur->next->val);
                cur = cur->next;
            } else {
            // find duplicate
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
        }
        return head;
    }
    // -----------------------------------------------------------
    // o(n^2) s(1)
    ListNode *removeDuplicates(ListNode *head) {
        // Write your code here
        if (!head) {
            return nullptr;
        }
        // //merge
        // ListNode* newhead = insertSort(head);
        // // de-dup
        // return deDup(newhead);
        return insertSort(head);
    }
    ListNode* insertSort(ListNode* head) {
        ListNode* cur = head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode* search = &dummy;
        while (cur->next) {
            bool finddup = false;
            search = &dummy;
            while (search->next) {
                if (cur->next->val == search->next->val) {
                    if (cur->next == search->next) {
                        break;
                    }
                    finddup = true;
                    ListNode* tmp = cur->next;
                    cur->next = cur->next->next;
                    delete tmp;
                    break;
                }
                search = search->next;
            }
            if (!finddup) {
              cur = cur->next; 
            }
        }
        return head;
    }
    //
    // Better
    // O(n^2) s(1)
    ListNode *removeDuplicates(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode dummy(0);
        // dummy.next = head;
        ListNode* cur = head;
        ListNode* search = &dummy;
        // head->next = nullptr;
        while (cur) {
            // search in the dummy
            search = &dummy;
            while (search->next && search->next->val != cur->val) {
                search = search->next;
            }
            // find dup, continue, for next cur
            if (search->next && search->next->val == cur->val) {
                cur = cur->next;
                continue;
            }
            // add cur into dummy
            ListNode* next = cur->next;
            ListNode* tmp = search->next;
            search->next = cur;
            cur->next = tmp;
            cur = next;
        }
        return dummy.next;
    }
   };
   

Similar problems

x

Tags

x