Showing posts with label C. Show all posts
Showing posts with label C. Show all posts

Saturday, November 2, 2013

Linked List Interview Question

Recently, my friend asked me to write a basic program in C to add a indicator (e.g. any number or char) between the two nodes of the given linked list. He is asked this question in one of the job interviews.
The output of the program with the indicator of  99 is shown as below.



The code
/* 
 * File:   main.cpp
 * Author: bekoC
 */

//Some notes about my compilation errors:
//There are many ways to get a segfault, 
//at least in the lower-level languages such as C(++). 
//A common way to get a segfault is to dereference a null pointer:
//int *p = NULL;
//*p = 1;


#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

struct Node {
    int data;
    struct Node *next;
};

struct Node* insert(struct Node *head, int data) {
    struct Node *temp = (struct Node*) malloc(sizeof (struct Node)); // for the new node address is taken by malloc in heap
    temp->data = data;
    temp->next = NULL;
    if (head == NULL) {
        head = temp; // first node give the head temp's address
    } else {
        Node *temp1 = head;
        while (temp1->next != NULL) {
            temp1 = temp1->next;
        }
        temp1->next = temp;
    }
    return head;
}

struct Node* addIndicator(struct Node *head, int indicator) {
    struct Node *newNode, *scan;
    struct Node *temp1 = head;
    while (temp1 != NULL && temp1->next != NULL) {
        newNode = (struct Node*) malloc(sizeof (struct Node));
        newNode->data = indicator;
        newNode->next = temp1->next;
        temp1->next = newNode;
        temp1 = newNode->next;
    }
    return head;
}

void printList(struct Node *head) {
    //using recursion
    if (head == NULL) {
        return;
    }
    printf("%d  ", head->data);
    printList(head->next);
}

int main(int argc, char** argv) {
    struct Node *head = NULL; // head point to no address
    head = insert(head, 2);
    head = insert(head, 4);
    head = insert(head, 6);
    head = insert(head, 8);
    printList(head);
    printf("\n");
    //Adding a indicator which is 99
    int indicator = 99;
    head = addIndicator(head, indicator);
    printList(head);
    return 0;
}