Remove duplicates in a Linked List

 

Introduction

   Removing duplicates from a linked list is a popular interview question. Although its simple, some people may ask the implement the linked list as such along with this. Yes, you need to add items to the linked list, remove an item from the linked list to do the removeDuplicates function.

Problem

  Move step-by-step.  (The questions to ask before you start)

1. Is the linked list sorted?
2. How large is the linked list? Is the size of the linked list fixed?

The above questions are because of the following reasons,

1. sorted list means duplicates are found in single iteration. (just a single scan and remove)
2. huge list means – doing a easy sorting would help. Dynamic list means – no sorting, need to try other approaches like heap. If space allowed, you can use hash map

Always go with the brute force way. 2 for loop approach.

Solution

class List

{

    int data;

    List* next;

public:

    List(int d)

    {

        this->data = d;

        this->next = NULL;

    }

    void append(int item)

    {

        List* iter = this;

        while(iter->next != NULL) iter = iter->next;

        List* newNode = new List(item);

        iter->next = newNode;

    }

    void deleteNode(List*& node)

    {

        if(this == node)

        {

            List *tmp = node->next;

            node->data = node->next->data;

            node->next = node->next->next;

            delete tmp;

        } else {

            List *iter = this;

            while(iter && iter->next != node) iter = iter->next;

            if(iter != NULL) {

                iter->next = node->next;

                delete node;

                node = iter;

            }

        }

    }

    void remove_dup()

    {

        for(List *iter1 = this; iter1 != NULL; iter1 = iter1->next) {

            for(List *iter2 = iter1->next; iter2 != NULL; iter2 = iter2->next) {

                if(iter1->data == iter2->data) {

                    deleteNode(iter2);

                }

            }

        }

    }

    void printList()

    {

        List *iter = this;

        while(iter) {

            std::cout<<iter->data<<"->";

            iter = iter->next;

        }

    }

};

void main()

{

    List obj(10);

    List *ptr = &obj;

    obj.append(2);obj.append(3);obj.append(5);

    obj.append(3); obj.append(6);

    obj.append(2); 

    obj.deleteNode(ptr);

    obj.printList();

    obj.remove_dup();

    std::cout<<std::endl;

    obj.printList();

}

Things found while writing code:

• this pointer is const!! :) which means List *const this; u cannot change what it points to. But u can change the object inside it. const member function has it like, List const *const this;
• As we delete node using next pointers in the list, to free the pointer you should take a backup of the pointer.
• Base test cases must be run to catch errors: 2 nodes, 1 node, first node, last node.
• Reference to a pointer will help in modifying the pointer in a function.
• The above code is a O(n2) complexity. Brute force. Best way is to do merge sort. – O(n log n) and when doing the merge, remove duplicates.

References

http://analgorithmaday.blogspot.in/2011/01/merge-lists-without-using-extra-space.html

http://analgorithmaday.blogspot.in/2011/01/merge-algorithm.html

http://analgorithmaday.blogspot.in/2011/01/merge-sort.html

Implement Queue using Linked List

 

Question

  Implement Queue using singly linked list. Enqueue should take O(1) time and Dequeue should take O(1) time.

Concept

  Unlike stack, for queues, we need two pointers: first and last. Enqueue will happen in last. Dequeue will happen in the first. Initially first and last both will point to the one node. After that every enqueue will have insertion happen at last->next.

Dequeue will happen at the first. If first and last both are equal, both will equal to NULL.

Code

class QueueList

{

    struct ListNode

    {

        int data;

        ListNode* next;

    };

    ListNode *first, *last;

public:

    QueueList() : first(NULL), last(NULL) { }

    void enqueue(int data);

    int dequeue();

};

void QueueList::enqueue(int data)

{

    ListNode *n = new ListNode;

    n->data = data;

    if(first == NULL && last == NULL)

    {

        first = last = n;

    }

    last->next = n;

    n->next = NULL;

    last = n;

}

int QueueList::dequeue()

{

    if(first == NULL && last == NULL) return -1;

    int data = first->data;

    ListNode* next = first->next;

    if(first == last) {

        free(last); 

        last = NULL;

    } else {

        free(first);

    }

    first = next;

    return data;

}

void main()

{

    QueueList obj;

    obj.enqueue(10);

    obj.enqueue(20);

    obj.enqueue(30);

    obj.enqueue(40);

    cout<<obj.dequeue();

    cout<<obj.dequeue();

    cout<<obj.dequeue();

    cout<<obj.dequeue();

    obj.enqueue(20);

    cout<<obj.dequeue();

    cout<<obj.dequeue();

}

Implement a Stack using Linked List

 

Question

  You need to implement a stack using singly linked list so that POP and PUSH takes O(1) similar performance of an array. How would you do that?

Concept

  We know about LIFO in a stack. We have to just maintain the element added to the linked list at the top. Then you will get a PUSH at the top with O(1) and POP at the top with O(1).

Code

class StackList 

{

    struct ListNode {

        int data;

        ListNode* next;

    };

    ListNode *head;

public:

    StackList() : head(NULL) {}

    void push(int data);

    int pop();

};

void StackList::push(int data)

{

    ListNode* n = new ListNode;

    n->data = data;

    n->next = head;

    head = n;

}

int StackList::pop()

{

    if(head == NULL)

        return -1;

    int tdata = head->data;

    ListNode* next = head->next;

    free(head);

    head = next;

    return tdata;

}

void main()

{

    StackList obj;

    obj.push(5);

    obj.push(3);

    obj.push(2);

    obj.push(10);

    cout<<obj.pop();

}

• Add elements to the head node
• Remove elements also from the head node

Reverse a linked list–Using Recursion

 

Introduction

   To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion without using extra space”.

The fun here is, we have to first understand the sequential concept to understand recursive. But if you understand sequential and do recursive based on it, you will be nowhere near to the correct solution.

  As recursion uses stack to store the arguments, we must decide what to store in the stack on each call to get the right linking done.

Concept

   In recursive approach, we need to move to the end of the node. But we must stop just before the end of the node, and we should have total 3 nodes in hand.

head (stack)                             head->next (not null)                head->next->next

head is what is in the stack. head->next->next will always be NULL. If it is not NULL, recursion continues. This is the base condition for our recursion.

if(!(head && head->next))

recur(head->next);

if head and head->next, both are not NULL.. don’t return. Recursion goes on until we get the last two nodes. but note that, in last recursion where we return, we will have something like this,

                                                     head                                    head->next 

here, head->next->next is NULL and the recursion returns since we are in the above situation.

now, we connect head->next->next to head. and set head->next to NULL. since, we have pushed the traversed head’s in the stack. In the next return, we will get,

              head  =>   head->next                           NULL <= result->next <= result

Note the change in the above address field location. Now, we have created two lists, one in reverse and un-reversed in forward direction. The important properties of these two lists and also loop invariants are,

• The reverse direction list always ends with NULL.
• The forward direction list always ends with the last node of the reversed list

This is why, we always get head->next->next as NULL. Which we again point it to head.

In this recursion, we have backed up root of the reversed list as return value. head->next as the argument and we always do head->next->next to make sure that, we get a valid 3 element entry.

Code

List* recur_rlist(List* head)

{

    List* result;

    if(!(head && head->next)) 

        return head;

    result = recur_rlist(head->next);

    head->next->next = head;

    head->next = NULL;

    return result;

}

void printList(List* head)

{

    while(head != NULL) {

        std::cout<<head->data<<" ";

        head = head->next;

    }

}

void main()

{

    List* list = createNode(2);

    append(list, createNode(3));

    append(list, createNode(4));

    append(list, createNode(5));

    append(list, createNode(6));

    List* revlist = recur_rlist(list);

    printList(revlist);

}

Important notes:

• Thanks to code snippet present in: http://www.daniweb.com/software-development/c/code/216620
• The major confusion comes in this because, we see the list from the reverse rather than from the forward as we do in a non-recursive routine
• After that confusion is solved, we need to make sure what is stored in the stack and what is returned?
• Note that ONLY THE ARGUMENT IS STORED IN THE STACK. So, we must be very careful in deciding what to store on the stack
• Note that, the head stored as argument in further recursion will always have head->next and head->next->next as valid pointers. This is made sure by the recursions base condition.
• If there is only one node, there is no need to reverse the list. So, its ok to check for head and head next both being non-NULL are not. If any one of it becomes NULL, we can blindly return the head recorded.
• reverse list always has the last node next set to NULL. So, from the forward list, we pop the last node part of the recursion and simple insert into head->next->next which pushes the last node of forward list into backward list
• The same approach if needs to be done without recursion requires a stack :)