Loading....
Coupon Accepted Successfully!

 

Question 11

How do you reverse a linked list without using any C pointers?
 


One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list).


Question 12

How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.
 


This is also one of the classic interview questions

There are multiple answers to this problem. Here are a few C programs to attack this problem.

Brute force method

Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.


typedef struct node
{
  void *data;
  struct node *next;
}mynode;
 

mynode * find_loop(NODE * head)
{
  mynode *current = head;

  while(current->next != NULL)
  {
    mynode *temp = head;
    while(temp->next != NULL && temp != current)
    {
      if(current->next == temp)
      {
        printf("\nFound a loop.");
        return current;
      }
      temp = temp->next;
    }
    current = current->next;
  }
  return NULL;
}




Visited flag

Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method

Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code


p=head;
q=head->next;

while(p!=NULL && q!=NULL)
{
  if(p==q)
  {
    //Loop detected!
    exit(0);
  }
  p=p->next;
  q=(q->next)?(q->next->next):q->next;
}

// No loop.




Question 13

How do you find the middle of a linked list? Write a C program to return the middle of a linked list
 


Another popular interview question

Here are a few C program snippets to give you an idea of the possible solutions.

Method1


p=head;
q=head;

if(q->next->next!=NULL)
{
  p=p->next;
  q=q->next->next;
}

printf("The middle element is %d",p->data);



Here p moves one step, where as q moves two steps, when q reaches end, p will be at the middle of the linked list.



Method2


struct node *middle(struct node *head)
{
  struct node *middle=NULL;
  int i;
 
  for(i=1; head; head=head->next,i++)
  {
     if(i==1)
        middle=head;
     else if ((i%2)==1)
        middle=middle->next;
   }
   
   return middle;
}



In a similar way, we can find the 1/3 th node of linked list by changing (i%2==1) to (i%3==1) and in the same way we can find nth node of list by changing (i%2==1) to (i%n==1) but make sure ur (n<=i).


Question 14

If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
 


The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

Check out the C program to implement a Generic linked list in the same FAQ.


Question 15

How to compare two linked lists? Write a C program to compare two linked lists.
 


Here is a simple C program to accomplish the same.


int compare_linked_lists(struct node *q, struct node *r)
{
    static int flag;
    
    if((q==NULL ) && (r==NULL))
    {
         flag=1;
    }
    else
    {
        if(q==NULL || r==NULL)
        {
            flag=0;
        }
        if(q->data!=r->data)
        {
            flag=0;
        }
        else
        {
           compare_linked_lists(q->link,r->link);
        }
    }
    return(flag);
}




Another way is to do it on similar lines as strcmp() compares two strings, character by character (here each node is like a character).






Test Your Skills Now!
Take a Quiz now
Reviewer Name