Insert a node in a sorted linked list.

Solution #1: Below is the code to insert a node in a linked list sorted in ascending order. The code assumes that the list is not empty initially.

void insert_sorted(struct node** pHead, int n)
{
    struct node* curr = *pHead;
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = n;

    if(*pHead == NULL)
    {
        temp->next = NULL;
        *pHead = temp;
        return;
    }

    if(curr->data > n)
    {
        temp->next = curr;
        *pHead = temp;
        return;
    }

    while(curr->next != NULL)
    {
        if((curr->data < n) && (curr->next->data > n))
            break;

        curr = curr->next;
    }

    temp->next = curr->next;
    curr->next = temp;
}

Given an array of unsigned integers which is initially increasing and then decreasing, find the maximum value in the array.

Solution #1: This problem can be solved in O(log n) by modifying binary search as follows,

int search(int* arr, int strt, int end)
{
    int mid = (strt+end)/2;

    if((arr[mid-1] < arr[mid]) &&  (arr[mid] > arr[mid+1]))
        return arr[mid];
    else if(arr[mid-1] < arr[mid])
        return search(arr, mid+1, end);
    else if(arr[mid] > arr[mid+1])
        return search(arr, strt, mid-1);
}

int main()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4};

    printf("%d\n", search(arr, 0, 9));
    return 0;
}