Common Interview Questions - Linked Lists

The following is a list of questions I have compiled based on my interviewing experience and several books:

Linked Lists:

1.  How do you implement  linked-list in an object-oriented language?
2. Write an algorithm to insert at the beginning of the list.
3. Write an algorithm to find a value in a list.
4. Write an algorithm to insert at the end of the list.
5. Write an algorithm to delete an element from a list.
6. Find the mth to the last element.[1]
7. Determine whether a list has a loop(is cyclic).[1]
8. Remove duplicates from a linked list.
9. Add two integers stored in  linked-lists, where each digit is stored in a separate element. Store the result as a linked-list where each digit is stored in a separate node.[2]

In bold : very probable question, that constitutes the required minimum.

You should determine if the linked list is singly-linked, doubly-linked or circularly-linked list. For this post, we will use only singly-linked lists.

1. How do you implement linked-list in an object-oriented language?
class ListElement{
                                 ListElement next;
                                 int data;
                                 ListElement ListElement(int data){ this.data=data; }
}

The implementation above is a singly-linked list and for simplicity it is assumed that the elements contain integer as a data, although data can be an object or a set of objects of any type.

2. Write an algorithm to insert at the beginning of the list.
ListElement LLInsertFront(ListElement head, int data){
ListElement e=new ListElement(data);
e.next=head;
return e;
}

You should not loose the pointer to the head of the list, therefore the method returns the new element.

3. Write an algorithm to find a value in a list.
          bool   LLFind(ListElement head, int data)
{
while (head!=null) if head.data==data return true;
                                else head=head.next;
return false;
}                                                                       

4. Write an algorithm to insert at the end of the list.
void LLInsertTail(ListElement head, int data)
{
while (head.next!=null) head=head.next;
ListElement e=new ListElement(data);
head.next=e;
}

5. Write an algorithm to delete an element from a list.
bool LLDelete(ListElement head, ListElement d)
{
if (head==d) {
                            head=head.next; 
                            delete d; 
                           return true;
                     }
while (head.next!=null)
{
   if (head.next==d) 
       { head.next=d.next;
          delete d;
           return true;
        }

}

6. Find the mth to the last element.
The idea is to use two pointers - A and B, that are m elements apart.
6.1.[Find the mth to the last element] Set the two pointers at the beginning of the list A=B=head;
6.2. Advance pointer B m times.
6.3. Start advancing pointer A and B by 1, checking every time if pointer B has reached the end of the linked list. When pointer B reaches the end, pointer A has the mth to the last element.

7.Determine whether a list has a loop(is cyclic).
The idea is to use two pointers A and B, advancing at a different rates. The fast pointer A moves 2 elements ahead, while the slow pointer B moves 1 element ahead. If the fast pointer reaches the last element, then the list does not contain a loop. Since the fast pointer advances 2 element ahead, you need to check for null the pointer as well as A.next. If the fast pointer reaches the slow pointer, that means the list contains a loop (again you need to check A.next=B as well as A=B).

8. Remove duplicates from a linked list.
Three basic methods exist:
- using two loops - unfavorable time complexity.  The inner loop should check only the element prior to the current element in the outer loop.
- using Hash table - additional memory is needed to store the hash table.
- using a sort algorithm - the original order of the linked list is not preserved.

9. Add two integers stored in  linked-lists, where each digit is stored in a separate element. Store the result as a linked-list where each digit is stored in a separate node. The digits are stored in reversed order.

Example adding (6,0,1) and (5,1,3) will produce (1,2,4). Here is an implementation using recursion:

ListNode AddInt(ListNode a, ListNode b, int carry)
{
int result=carry;
if (a!=null) result+=a.data;
if (b!=null) result+=b.data;
if (a==null) && (b==null) return null;
ListNode n=new ListNode(result%10);
n.next=AddInt(a.next, b.next, result>10?1:0);
return n;
}

Sources:
1. "Programming Interviews Exposed" 2nd Edition, published 2007, John Mongan, Noah Soujanen, Eric Giguere ISBN: 978-0-470-12167-2
2. "Coding Interview" 4th Edition, Gayle Laakmann, 2010, ISBN 978-1451578270,