Insertion & Deletion

Some Tricky Problems

Flatten a MultiLevel DLL

Convert something like this:

//  1---2---3---4---5---6--NULL
//          |
//          7---8---9---10--NULL
//              |
//              11--12--NULL

To : *[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]*

 Node *flattenIt(Node *head)
    {
        if (!head)
            return NULL;
        Node *curr = head;
        Node *tail = head;
        while (curr)
        {
            Node *ahead = curr->next;
            if (curr->child)
            {
                Node *newHead = curr->child;
                Node *childTail = flattenIt(newHead);

                curr->next = newHead;
                newHead->prev = curr;

                if (ahead)
                {
                    ahead->prev = childTail;
                    childTail->next = ahead;
                }
                curr->child = NULL;
                tail = childTail;
            }
            else
                tail = curr;
            curr = ahead;
        }
        return tail;
    }
    Node *flatten(Node *head)
    {
        flattenIt(head);
        return head;
    }

Remove Duplicates from Sorted DLL

 ListNode *removeDuplicates(ListNode *head)
    {
        if (!head)
            return NULL;

        ListNode *temp = head;
        while (temp && temp->next)
        {
            ListNode *ahead = temp->next;
            while (ahead && ahead->val == temp->val)
            {
                ListNode *duplicate = ahead;
                ahead = ahead->next;
                delete duplicate;
            }

            temp->next = ahead;
            if (ahead)
                ahead->prev = temp;
            temp = temp->next;
        }
        return head;
    }