Behavioral Data Structure Linked list Interview Questions & Answers:

1. Explain the most efficient method to reverse a linked list?

To call the function:
newHead = reverse(head);

struct Node *reverse(Node *curp)
{
static struct Node *head = curp;
static struct Node *revHead = NULL;
if (curp == NULL)
return NULL;
if (curp->next == NULL)
revHead = curp;
else
reverse(curp->next)->next = curp;
if (curp == head) {
curp->next = NULL;
return revHead;
}
else
return curp;
}

2. Do you know how to reverse String in Java?

This is one of my favorite question. Since String is one of the most important type in programming, you expect lot of question related to String any data structure interview. There are many ways to reverse Sting in Java or any other programming language, and interviewer will force you to solve this problem by using without API i.e. without using reverse() method of StringBuffer. In follow-up he may ask to reverse String using recursion as well. See 3 ways to reverse String in Java to learn reversing String using both loops and recursion in Java.

3. Suppose In an integer array, there is 1 to 100 number, out of one is duplicate, how to find?

This is a rather simple data structures question, especially for this kind of. In this case you can simply add all numbers stored in array, and total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number. Of course there is a brute force way of checking each number against all other numbers, but that will result in performance of O(n^2) which is not good. By the way this trick will not work if array have multiple duplicates or its not numbers forming arithmetic progression. Here is example of one way to find duplicate number in array.

4. Explain how to find 3rd element from end in a linked list in one pass?

This is another frequently asked linked list interview question. This question is exactly similar to finding middle element of linked list in single pass. If we apply same trick of maintaining two pointers and increment other pointer, when first has moved upto 3rd element, than when first pointer reaches to the end of linked list, second pointer will be pointing to the 3rd element from last in a linked list.

5. Do you know how to find if linked list has loop?

This question has bit of similarity with earlier algorithm and data structure interview question. I mean we can use two pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to same node. This will only happen if linked list has loop.

6. Tell me how to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview. Since many programmer know that, in order to find length of linked list we need to first traverse through linkedlist till we find last node, which is pointing to null, and then in second pass we can find middle element by traversing only half of length. They get confused when interviewer ask him to do same job in one pass. In order to find middle element of linked list in one pass you need to maintain two pointer, one increment at each node while other increments after two nodes at a time, by having this arrangement, when first pointer reaches end, second pointer will point to middle element of linked list. See this trick to find middle element of linked list in single pass.

7. Do you know what does the following function do for a given Linked List?

void fun1(struct node* head)
{
if(head == NULL)
return;

fun1(head->next);
printf("%d ", head->data);
}
fun1() prints the given Linked List in reverse manner. For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1.

8. By using C++ with an example describe linked list?

To use a linked list in C++ the following structure is to be declared:

typedef struct List
{long Data;
List* Next;
List ()
{Next=NULL;
Data=0;
}
};
typedef List* ListPtr.

The following code snippet is used to add a node.

void SLList::AddANode()
{ListPtr->Next = new List;
ListPtr=ListPtr->Next;
}

The following code snippet is used to traverse the list

void showList(ListPtr listPtr)
{
while(listPtr!=NULL) {
cout<<listPtr->Data;
}
return temp;
}

9. What is linked list?

A linked list is a chain of nodes. Each and every node has at least two nodes, one is the data and other is the link to the next node. These linked lists are known as single linked lists as they have only one pointer to point to the next node. If a linked list has two nodes, one is to point to the previous node and the other is to point to the next node, then the linked list is known as doubly linked list.

10. Tell me about circular linked list?

An array of pointers is an array consisting of pointers. Here, each pointer points to a row of the matrix or an element. E.g char *array [] = {"a", "b"}. This is an array of pointers to to characters.