兩個有序連結串列序列的合併

2022-09-22 18:42:58 字數 1213 閱讀 5110

標籤(空格分隔): 資料結構 演算法競賽

02-線性結構1 兩個有序連結串列序列的合併(15 分)

本題要求實現一個函式,將兩個連結串列表示的遞增整數序列合併為一個非遞減的整數序列。

函式介面定義:

list merge( list l1, list l2 );

其中list結構定義如下:

typedef struct node *ptrtonode;

struct node ;

typedef ptrtonode list; /* 定義單連結串列型別 */

l1和l2是給定的帶頭結點的單連結串列,其結點儲存的資料是遞增有序的;函式merge要將l1和l2合併為一個非遞減的整數序列。應直接使用原序列中的結點,返回歸併後的帶頭結點的連結串列頭指標。

裁判測試程式樣例:

#include #include typedef int elementtype;

typedef struct node *ptrtonode;

struct node ;

typedef ptrtonode list;

list read(); /* 細節在此不表 */

void print( list l ); /* 細節在此不表;空連結串列將輸出null */

list merge( list l1, list l2 );

int main()

/* 你的**將被嵌在這裡 */

輸入樣例:

31 3 5

52 4 6 8 10

輸出樣例:

1 2 3 4 5 6 8 10

null

null

下面附上**,因為是第一次學連結串列,寫了三四個小時才明白並完全寫對。

list merge(list l1,list l2) 

else

l=l->next;

}l->next=

null;

if (ll1) l->next=ll1;

else

if (ll2) l->next=ll2;

l1->next=

null;

l2->next=

null;

//當此時,由於l是一直移動的指標,所以它並不是連結串列頭,只有它的初始值l0才是連結串列頭。

return l0;

}