連結リスト版マージソートの問題をやっていますが、なかなか難しくてできません。
穴埋め式なのでわかるところは一応埋めましたが、
とくに*merge_sort_lst関数のreturn文の処理のところは
再帰を用いるのですがイマイチ正解が思いつきません。
返答のほどよろしくお願いいたします。
#include <stdio.h>
#include"AlgDat.h"
#define  N 8

/* 連結リストのセルは AlgDat.h に定義 */

struct CELL *merge_lst(struct CELL *a, struct CELL *b); /* 連結リストマージ */
struct CELL *merge_sort_lst(struct CELL *x);      /* 連結リストマージソート */
/* showlst は AlgDat.h に定義 */

void main(void)
{
    struct CELL lst0, lst1, lst2, lst3, lst4, lst5, lst6, lst7;
    
    /* 連結リストの初期化 */
    lst0.value = 20; lst0.next = &lst1;
    lst1.value =  8; lst1.next = &lst2;
    lst2.value =  3; lst2.next = &lst3;
    lst3.value = 15; lst3.next = &lst4;
    lst4.value = 24; lst4.next = &lst5;
    lst5.value = 27; lst5.next = &lst6;
    lst6.value = 19; lst6.next = &lst7;
    lst7.value = 10; lst7.next = NULL;
    
    printf("マージソート前 lst ");
    showlst(&lst0);
    
    printf("マージソート後 lst ");
    showlst(merge_sort_lst(&lst0));
}

/* 連結リスト x のマージソート
   引数   : 連結リスト x のアドレス
   戻り値 : 整列された連結リストの先頭要素へのポインタ */
struct CELL *merge_sort_lst(struct CELL *x)
{
    struct CELL *a, *b, *p;
    
    if (x == NULL || x -> next == NULL)      /* 連結リストが空 or １つならば */
        return(x);                           /* 何もしないでリターン */
    
    /* <----- 連結リストの分割開始 */
    /* 連結リストをスキャンするポインタの初期化 */
    a = x;                                   /* a は１番目の要素を指す */
    
    b = x -> next;                           /* b は３番目の要素を指す */
    if(b != NULL)                            /* 連結リストの長さが２ならば */
        b = b -> next;                       /* b は２番目の要素を指す */
    
    while(b != NULL){         /* ポインタ b が連結リストの末尾に到達するまで */
        a = a -> next;        /* ポインタ a は１つ進める */
        b = b -> next;
        if(b != NULL)
            b = b -> next;    /* ポインタ b を２つ進める */
    }                         /* ポインタ b が末尾に到達したとき, 
                                 ポインタ a は連結リストのほぼ中央を指すはず */
    
    /* 連結リストを a が指す要素直後で切断 */
    
    /***** ??? *****/;
    /***** ??? *****/;
    /* <----- 連結リストの分割終了 */
    
    /* 切断した連結リストを個別に整列し, その結果をマージ */
    return(/***** ??? *****/);
}

/* 連結リスト a と b をマージ
   引数   : 連結リスト a, b の各アドレス
   戻り値 : マージされた連結リストの先頭要素へのポインタ */
struct CELL *merge_lst(struct CELL *a, struct CELL *b)
{
    struct CELL header;
    struct CELL *p;                    /* マージ済列最後尾を指すポインタ */
    
    p = &header;                       /* 初期値はダミーの要素を指す */
    
    while(/***** ??? *****/){          /* 連結リストのいずれかが空になるまで */
        if(/***** ??? *****/){         /* 先頭の要素を比較 */
            p -> next = a;             /* 連結リスト a の先頭要素を取り除き */
            p = a;                     /* マージ済み連結リストの末尾に連結  */
            a = a -> next;
        }
        else {
           p -> next = b;              /* 連結リスト b の先頭要素を取り除き */
           p = b;                      /* マージ済み連結リストの末尾に連結  */
           b = b -> next;
       }
    }
    
    /* 残っている要素をマージ済み連結リストの最後尾に連結 */
    if (a == NULL)
        p -> next = b;
    else
        p -> next = a;
    return(/***** ??? *****/);      /* マージ済み連結リストを関数値として返す */
}

/*
    AlgDat.h
    Update 2004.5.10
    Definitions for Algorithm and Data structure
*/
/* 連結リストのセル */
struct CELL {
    int    value;      /* 実際のデータ */
    struct CELL *next; /* 次のセルへのポインタ */
};

void showary(int a[], int n);       /* 大きさ n の配列を表示 */
void showlst(struct CELL *x); /* 連結リストの表示 */

void showary(int a[], int n)
{
    int i;
    
    for(i = 0; i < n; i++)
        printf("%2d ", a[i]);
    printf("\n");
}

void showlst(struct CELL *x)
{
    struct CELL *p;
    
    for(p = x; p != NULL; p = p -> next)
        printf("%2d ", p -> value);
    printf("\n");
}

正解をずばり書いてしまうのも気が引けますので、微妙に変更を加えたコードを掲げます。
アルゴリズムはいじってませんので、丹念にコードを追ってください。

#include <stdio.h>

#define SIZE 8

typedef struct cell_type{
    int dat;
    struct cell_type* next;
}Cell;

void show( Cell* p );
Cell* merge( Cell* x, Cell* y );
Cell* merge_sort( Cell* s );

const int DATA[SIZE] = {20,8,3,15,24,27,19,10};

int main( void )
{
    Cell cell[SIZE];
    int i;
    for( i = 0; i < SIZE; i++ ){
        cell[i].dat = DATA[i];
        if( i < SIZE - 1 ){
            cell[i].next = &cell[i+1];
        }
    }
    cell[SIZE-1].next = NULL;

    printf( "ソート前 : " );
    show( &cell[0] );

    printf( "ソート後 : " );
    show( merge_sort( &cell[0] ) );

    return 0;
}

void show( Cell* p )
{
    for( ; p != NULL; p = p->next ){
        printf( "%2d ", p->dat );
    }
    putchar( '\n' );
}

Cell* merge( Cell* x, Cell* y )
{
    Cell dummy;
    Cell* p = &dummy;

    while( x != NULL && y != NULL ){
        if( x->dat <= y->dat ){
            p->next = x;
            p = x;
            x = x->next;
        }
        else{
            p->next = y;
            p = y;
            y = y->next;
        }
    }

    if( x == NULL ){
        p->next = y;
    }
    else{
        p->next = x;
    }

    return dummy.next;
}

Cell* merge_sort( Cell* s )
{
    Cell* x, * y, * t;
    if( s == NULL || s->next == NULL ){
        return s;
    }

    x = s;
    y = s->next;
    if( y != NULL ){
        y = y->next;
    }

    while( y != NULL ){
        x = x->next;
        y = y->next;
        if( y != NULL ){
            y = y->next;
        }
    }

    t = x->next;
    x->next = NULL;

    return merge( merge_sort( s ), merge_sort( t ) );
}

/* 実行結果：
ソート前 : 20  8  3 15 24 27 19 10
ソート後 :  3  8 10 15 19 20 24 27
*/