Linked list where user replace a chosen number in the list with a number chosen by user - how can it be improved?
For a new user of C you really aren't doing too bad, you're not using global variables which is very good. The functions are small and well defined. The program as a whole is well organized so that function prototypes are not required.

This program could have a few more function and that would simplify main():


A function that asks the user for input and performs error checking on the input before returning values, this would also localize the variables for input in the function   
There are some basic linked list operations that are not here that might be helpful insert_node(), delete_node() and append_node() find_node(), other functions such as replace() can utilize these basic functions  
It might be good to have a function that prints a title and then calls printlist() which would reduce the amount of code in main()  
A function to initialize the linked list  


Missing Error Checking

There are two places where error checking in this program, first, it is generally a best practice to error check all user input before using the input values. Users can make mistakes when entering data, they may just hit the enter key without entering data, they may enter a string instead of a number, they may enter a number that is not in the list which could cause problems while searching the list.

The second place where error checking is necessary is after any memory allocation in the C programming language, some or most high level languages will throw exceptions if memory allocation fails. In C programming if memory allocation fails the call to malloc(), calloc() or realloc() returns NULL. It is very important to check the value returned to make sure it is not NULL before using the memory, access through a NULL pointer causes unknown behavior. This can cause a number of problems including the crashing of the program or the corruption of data in the program.

node_t *create_new_node(int val) {
    node_t *result = malloc(sizeof(node_t));
    if (result == NULL)
    {
        fprintf(stderr, "malloc failed in create_new_node()\n");
        return result;
    }
    result-&gt;val = val;  // Unknown behavior here if malloc() failed
    result-&gt;next = NULL;
    return result;
}


Include Files That Are Not Necessary

The code contains #include &lt;string.h&gt; however, no functions defined in this include file are utilized. The `#include  statement copies the contents of the file into the current file, it will increase the compile time and if you are using an editor that also creates a makefile it may add an unnecessary dependency to the makefile. There may also be collisions with functions defined in the code. Basically don't include files you don't need.

Return From Main

The C compiler is smart enough to add return 0; at the end of this program, if the code does contain multiple returns from main() such as program failure when malloc() fails the code will be more readable if return EXIT_FAILURE; or return EXIT_SUCCESS;. These macros are included from stdlib.h which is already included in this program.

Readability

The code would be more readable and easier to maintain if there were spaces between operators and operands for (int i=0; i&lt;25; i++) { versus for (int i = 0; i &lt; 25; i++) {. It would also make the code more readable and maintainable if the 25 in the for loop was a symbolic constant

#define LIST_SIZE 25

...

    for (int i = 0; i &lt; LIST_SIZE; i++) {
        tmp = create_new_node(i);
        if (tmp == NULL)
        {
            return EXIT_FAILURE;
        }
        tmp-&gt;next = head;
        head=tmp;
    }