Compare two linked lists

Linked list Interview Question

Compare two linked lists

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format

You have to complete the int CompareLists(Node* headA, Node* headB) method which takes two arguments - the heads of the two linked lists to compare. You should NOT read any input from stdin/console.

Output Format
Compare the two linked lists and return 1 if the lists are equal. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

NULL, 1 --> NULL
1 --> 2 --> NULL, 1 --> 2 --> NULL

Sample Output

0
1
Explanation 
1. We compare an empty list with a list containing 1. They don't match, hence return 0. 
2. We have 2 similar lists. Hence return 1.

int CompareLists(Node *headA, Node* headB)
{
    int flag=0;
  // This is a "method-only" submission. 
  // You only need to complete this method 
    while(headA!=NULL)
        {
        if(headA->data==headB->data)
            {
            flag=1;
        }
        else
            {
            flag=0;
            break;
        }
        headA=headA->next;
        headB=headB->next;
    }
    if(headB!=NULL)
        {
        flag=0;
    }
    return flag;
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Intersection in a given linked list

Linked list Interview Question

Intersection in a given linked list

Given pointers to the head nodes of linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL.
In the diagram below, the two lists converge at Node x:

[List #1] a--->b--->c
                     \
                      x--->y--->z--->NULL
                     /
     [List #2] p--->q

Complete the int FindMergeNode(Node* headA, Node* headB) method so that it finds and returns the data value of the Node where the two lists merge.
Input Format
The FindMergeNode(Node*,Node*) method has two parameters, and , which are the non-null head Nodes of two separate linked lists that are guaranteed to converge.
Do not read any input from stdin/console.
Output Format
Each Node has a data field containing an integer; return the integer data for the Node where the two lists converge. Do not write any output to stdout/console.
Sample Input
The diagrams below are graphical representations of the lists that input Nodes and are connected to. Recall that this is a method-only challenge; the method only has initial visibility to those Nodes and must explore the rest of the Nodes using some algorithm of your own design.

Test Case 0

 1
  \
   2--->3--->NULL
  /
 1
Test Case 1

1--->2
      \
       3--->Null
      /
     1
Sample Output

2
3
Explanation

Test Case 0: As demonstrated in the diagram above, the merge Node's data field contains the integer  (so our method should return ). 

Test Case 1: As demonstrated in the diagram above, the merge Node's data field contains the integer  (so our method should return ).


int FindMergeNode(Node *headA, Node *headB)
{
    // Complete this function
    // Do not write the main method.
    int a=0,b=0;
    struct Node* temp = headA;
    while(temp)
        {
        a++;
        temp=temp->next;
    }

    temp = headB;
    while(temp)
        {
        b++;
        
        temp=temp->next;
    }
   
    if(a>b)
        {
        a-=b;
        while(a)
            {
            headA=headA->next;
            a--;
        }
        while(headA==headB)
            {
            headA=headA->next;
             headB=headB->next;
        }
        return headA->data;
    }
    else
        {
        a=b-a;
        while(a!=0)
            {
            
            headB=headB->next;
            a--;
           
        }
        while(!(headA == headB))
            {
           
             headA=headA->next;
             headB=headB->next;
        }
             return headA->data;

    }
    return 0;
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Reverse of a given linked list

linked list Interview Question

Reverse of a given linked list

You’re given the pointer to the head node of a linked list. Change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

Input Format
You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console.
Output Format
Change the next pointers of the nodes that their order is reversed and return the head of the reversed linked list. Do NOT print anything to stdout/console.
Sample Input
NULL
2 --> 3 --> NULL

Sample Output
NULL
3 --> 2 --> NULL

Node* Reverse(Node *head)
{
  // Complete this method
    struct Node* prev = NULL;
    struct Node* next = NULL;
    while(head!=NULL)
        {
        next = head->next;
        head->next=prev;
        prev=head;
        head=next;
    }
    head=prev;
    return head;
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Insert Node at nth position in a linked list

linked list Interview Question

Insert Node at nth position in a linked list

You’re given the pointer to the head node of a linked list, an integer to add to the list & the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node. A position of zero indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Input Format

You have to complete the Node Insert(Node* head, int data, int position) method which takes three arguments the head of the linked list, the integer to insert and the position at which the integer must be inserted. You should NOT read any input from stdin/console. position will always be between 0 and the number of the elements in the list.

Output Format
Insert the new node at the desired position and return the head of the updated linked list. Do NOT print anything to stdout/console.
Sample Input
NULL, data = 3, position = 0
3 --> NULL, data = 4, position = 0
Sample Output

3 --> NULL
4 --> 3 --> NULL
Explanation

1. we have an empty list and position 0. 3 becomes head.
2. 4 is added to position 0, hence 4 becomes head.

Node* InsertNth(Node *head, int data, int position)
{
  // Complete this method only
  // Do not write main function. 
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node*));
    newnode->data=data;
    newnode->next=NULL;
    struct Node*  ptr = head; 
    if(ptr==NULL)
        {
        head = newnode;
        return head;
    }
    else if(position==0)
        {
        newnode->next=head;
        head=newnode;
        return head;
    }
    else
        {
        while(position>1)
        {   
            ptr=ptr->next;
            position--;
        }
        if(ptr->next==NULL)
        {
            ptr>next=newnode;
        }
        else
        {
            newnode>next=ptr->next;
            ptr->next=newnode;
        }
        return head;
    }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

linked list Interview Question

Hey guys i am providing the solution to the most comman linked list question asked in interview as linked list is most important data structure from interview point of view.All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 1
Print the nodes of the given linked list?

Solution
click here to find the solution

Question 2
Insert the nodes at the given position in linked list?

Solution
click here to find the solution

Question 3
Find the intersection in a given linked list?

Solution
click here to find the solution

Question 4
Reverse a linked list?

Solution
click here to find the solution

Question 5
Compare two linked list

Solution
click here to find the solution

Read More

How to print the node of the given linked list

Linklist Interview Question

How to print the node of the given linked list

If you're new to linked lists, this is a great exercise for learning about them. Given a pointer to the head node of a linked list, print its elements in order, one element per line. If the head pointer is null (indicating the list is empty), don’t print anything.

Input Format
The void Print(Node* head) method takes the head node of a linked list as a parameter. Each struct Node has a data field (which stores integer data) and a next field (which points to the next element in the list).

Note: Do not read any input from stdin/console. Each test case calls the Print method individually and passes it the head of a list.

Output Format
Print the integer data for each element of the linked list to stdout/console (e.g.: using printf, cout, etc.). There should be one element per line.

Sample Input
This example uses the following two linked lists:
NULL
1->2->3->NULL
and are the two head nodes passed as arguments to Print(Node* head).

Note: In linked list diagrams, -> describes a pointer to the next node in the list.

Sample Output

1
2
3
Explanation

Test Case 0: NULL. An empty list is passed to the method, so nothing is printed.

Test Case 1: 1->2->3->NULL. This is a non-empty list so we loop through each element and printing each element's data field on its own line.

Here i am only providing the main function you have to create the link list first then only you can print its nodes.

/*
  Print elements of a linked list on console 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
void Print(Node *head)
{
  // This is a "method-only" submission. 
  // You only need to complete this method. 
    while(head!=NULL)
        {
        cout<<head->data<<endl;
        head = head->next;
    }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More