I'm writing a function to recursively merge and sort a linked-list. (An improved merge-sort algorithm that avoids scanning the list.)

The function needs to return the sorted first half of the list and the rest of the list. The function is passed the length of the list as an argument n, it recursively calles itself with length n/2 to split the list into single elements before merging it back together in sorted order.

I think I have determined the algorithm that is required - i'm struggling with the C implementation.

As the function is required to return 2 values, I think I need to use a double pointer when calling the function. (So it can modify the calling pointer to point to the second half of the list.)

I have been provided with the following struct definition:

insert
Code:
typedef struct node Node;
typedef Node* Link;
struct node{int item; Link next;}
My interpretation of the line [typedef Node* Link] is that it defines the type Link to be a pointer, that points to something of type Node.

I'm struggling with the concept of using a double pointer to point to something that is already defined as a pointer.

Can anyone help me with which is the appropraite function prototype in order to have the pointer that is passed to the function, updated by the function? (it needs to return a pointer to a node in the linked list)

Link mergesort_no_scan(int n, Link **list)
-> this to me looks like a double pointer to something that is already a pointer (triple pointer?)

Link mergesort_no_scan(int n, Link *list)
-> Link is already a pointer. If I define the function like this am I calling the function with a double pointer?

Link mergesort_no_scan(int n, Node **list)
-> Or should I be avoiding using the Link pointer when calling the function, and passing the function a pointer to a pointer to a node instead?

Help! I'm totally confusing myself with all this pointer talk!