Linked List (1)

Linked List is a very important data structure in Firmware field. Almost all Firmware interviewers will ask at least 1  linked list question! Here are many linked list questions and their example solution. If you cannot understand the example solution in the first glance, you could draw the linked list on a paper to help you understand each line of code.
Before you go for a firmware interview, please make sure you can solve each question within 15 minutes. After practicing all of these questions (or most of them), you should be able to handle all linked list questions in your interview. 

Create Linked List

Node* Create()
{
    int input;
    Node *p0, *p1, *head;
    p0 = (Node*)malloc(sizeof(Node)); // create a dummy head
    p1 = p0;
 
    while (scanf("%d", &input)) {
        p1->next = (Node*)malloc(sizeof(Node));
        p1 = p1->next;
        p1->data = input;
    }
 
    p1->next = NULL;             // kill the dummy head now
    head = p0->next;
    free(p0);
 
    return head;
}

Insert an item to the head of a Linked List

int insert(node **head, int data)
{
    node *new;
    new = (node*)malloc(sizeof(node));
 
    new->value = data;
    new->next = *head;
    *head = new;
 
    return new->value;
}

Insert an item into a sorted Linked List: Ex.insert 4 into 1->3->7->8 => 1->3->4->7->8
Node* Insert_Sorted(Node *head, int value)
{
    Node *p0, *p1, *new;
    new = (Node*)malloc(sizeof(Node));
    new->data = value;
 
    p1 = head;
    while (p1 != NULL && p1->data <= value) {
        p0 = p1;
        p1 = p1->next;
    }
 
    if (p1 == head) {   // be careful Special Case! 
        head = new;     // may stop at the head!
        new->next = p1;
    }
    else {              // otherwise
        p0->next = new;
        new->next = p1;
    }    
 
    return head;
}