String (2)

Return the 1st non-repeated character: Ex."aaaaaaak47" return 'k'
char find_first_nonrepeat(char *str)  
{
    char *c1 = str;
    char pre_c = *c1;
 
    while (*c1 != '\0' && *c1 == pre_c)
    {       
        pre_c = *c1; // If the same as previous char,
        c1++;        // add c1 by 1 and go to next char
    }

    if (*c1 == '\0') // Be careful the special case!
        return 0;    // => all chars are the same
    else
        return *c1; // This is to return a char, not pointer                     
}

Convert an Integer to a String
char* num2str(int num, char *str)
{
    char *c, *c2;
    for (c = str; num; num/=10, c++)
        *c = num % 10 + '0';
    *c = '\0';
    c2 = c - 1;
    c = str;        // After that we need to reverse the string,
                    // since string c starts from lower digit.
    while (c < c2) {// It is a different way to reverse a string
        *c ^= *c2;    
        *c2 ^= *c;
        *c++ ^= *c2--;
    }
    return str;
}

Compare 2 strings. If equal return 1, else return 0
int Same(char *s1, char *s2)
{
    char *c1, *c2;
    c1 = s1;
    c2 = s2;
    while (*c1 != '\0' && *c2 != '\0' && *c1 == *c2) {
        c1++;
        c2++;
    }
    if (*c1 == '\0' && *c2 == '\0')
        return 1;  // If while loop goes to the end => equal
    else
        return 0;
}

Linked List (4)

Find the middle item in a Linked List

int find_middle(node *head)
{
    node *p1, *p2;
    p1 = p2 = head;
 
    while (p1 != NULL && p1->next != NULL) {
        p1 = p1->next->next; // p1 goes 2 steps; p2 goes 1 step
        p2 = p2->next;// when p1 to the end, p2 points to middle
    }
 
    return p2;
}

Determine if there is a loop in a Linked List
bool find_loop(node *head)
{
    node *p1, *p2;
    p1 = p2 = head;
 
    while (p1 != NULL && p1->next != NULL) {
        p1 = p1->next->next;// p1 goes 2 steps; p2 goes 1 step
        p2 = p2->next;
        if (p1 == p2) // If there is loop, we must get p1 == p2 
            return true;  // sooner or later
    }
 
    return false;     // If goes out of the while, no loop.
}

Find merge point of two Linked Lists (if there is one)
Node* Find_merge_point(Node *h1, Node *h2)
{
    Node *p1, *p2;
 
    int n = Length1(h1) - Length1(h2); 
    if (n >= 0) {  // make p1 to be longer one 
        p1 = h1;
        p2 = h2;
    }
    else {
        n *= -1;
        p1 = h2;
        p2 = h1;
    }
 
    while (n--)// n is the length diff. between p1 and p2
        p1 = p1->next; // make p1 and p2 "aligned" 
 
    while (p1 != p2 && p1 != NULL && p2 != NULL) {
        p1 = p1->next; // start to check merge point
        p2 = p2->next;
    }
 
    if (p1 == NULL || p2 == NULL) {
        printf("can't find merge point!\n");
        return NULL;
    }
    else
        return p1;
}

Linked List (3)

Sum up values of all items in a Linked List (items are integers)

int Sum(Node *head)
{
    if (head == NULL)
        return 0;
    else
        return head->data + Sum(head->next);
}

Print all items in a Linked List
void Print1(Node *head)
{
    if (head == NULL) // Special Case! head is null!
        return;
    else {
        printf("%d ", head->data);
        Print1(head->next);
    }
}

Reversely print all items
void Print(Node *head)
{
    if (head == NULL)
        return;
    else {
        Print(head->next);        // Recursively call itself, 
        printf("%d ", head->data);// so last one is printed first.

    }
}

Find the last Mth item: Ex.find the last 2th in 1->4->5->2->9->0->3->Null => 0
Node* Find_Mth_Last(Node **head, int M)
{
    Node *p1, *p2;
    p1 = *head;
 
    while (M >= 0 && p1 != NULL) { // p1 goes to Mth first
        p1 = p1->next;             
        M -= 1;
    }
 
    if (M != -1) {  // if we can find out, M == -1, not M == 0
        printf("can't find Mth, because its shorter than M!");
        return NULL;
    }
 
    p2 = *head;         // p2 points to 1st
    while (p1 != NULL) {// when p1 to the end, p2 points to Mth
        p1 = p1->next;    
        p2 = p2->next;
    }
 
    return p2;
}

Linked List (2)

Insert an item into a Circular Linked List

int insert_circular(node **head, int data)
{
    node *p1;
    node *new = (node*)malloc(sizeof(node));
    new->value = data;
 
    if (*head == NULL) { 
        *head = new;
        *head->next = *head;   // for circular linked list 
        return new->value;
    } 
 
    p1 = *head;
    while (p1->next != *head) {// find the node before head
        p1 = p1->next;
    }
 
    p1->next = new;            // insert head
    new->next = *head;
    *head = new;
 
    return new->value;
}

Insert an item into a Double Linked List
int insert_double(node** head, int num) 
{
 
        node *p0, *p1, *p2;
    p2 = (node*)malloc(sizeof(node));
    p2 -> data = num;         
    if (*head == null) {
        *head = p2;
        p2->prev = null;
        return num;
    }
    p1 = *head;
    while (p1 != NULL && p1->data > num) {
        p0 = p1;
        p1 = p1->next;
    }
    if (p1 == *head) {    // Special Case!
        p2->next = p1;
        p2->prev = NULL;
        *head = p2;
    }
    else {
        p0->next = p2;
        p2->prev = p0;
        p2->next = p1;
        if (p1 != NULL)
            p1->prev = p2;
    }
 
    return num;
}

Delete an item in a Linked List
Node* Remove(Node *head, int value)
{
    Node *p0, *p1, *temp;
    p1 = head;
 
    while (p1 != NULL && p1->data != value) {
        p0 = p1;
        p1 = p1->next;
    }
 
    if (p1 == NULL) {               // Special Case! can't find
        printf("can't find item\n");
    }
    else if (p1 == head) {       // Special Case! find out at head
        head = head->next;
        free(p1);
    }
    else {                       // otherwise
        p0->next = p1->next;
        free(p1);
    }
 
    return head;
}

Reverse a Linked List: Ex. 1->7->5->3->Null => 3->5->7->1->Null
Node* Reverse(Node* head)
{
    Node *p0, *p1, *temp;
    p0 = NULL;
    p1 = head;
 
    while (p1 != NULL) {// reverse linked list
        temp = p1->next;// you could draw a linked list on paper,
        p1->next = p0;  // to understand why it reverses the list.
        p0 = p1;
        p1 = temp;
    }
 
    return p0;       // if head == NULL, p0 is also NULL
}

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;
}