劍指offer 合併兩個排序的連結串列

2022-11-24 15:21:34 字數 1140 閱讀 7255

題目描述

輸入兩個單調遞增的連結串列,輸出兩個連結串列合成後的連結串列,當然我們需要合成後的連結串列滿足單調不減規則。

思路:建立一個頭節點,設兩個指標,分別指向兩個排好序的連結串列頭,比較大小。

1/*2

struct listnode 8};

*/9class

solution else

26 tmp->next = null; //

始終保持合併後的連結串列尾指向空27}

28if (tmp1 !=null) else

33return pmerge->next;34}

35 };

以下是不建立頭結點的做法:

1

class

solution

9if (phead2 ==null)

12 listnode *pmerge =null;

13 listnode *current = pmerge, *tmp1 = phead1, *tmp2 =phead2;

14while (tmp1 != null && tmp2 !=null) else

22 tmp1 = tmp1->next;

23 } else

else

30 tmp2 = tmp2->next;31}

32 current->next =null;33}

34if (tmp1 !=null) else

39return

pmerge;40}

41 };

可以看到第一個while迴圈中每次都要判斷是不是第一個結點,如果是第一個結點,就把它當作連結串列第一個結點,而不是連結串列的下一個結點。加了一個判斷,更耗時。

以上都是非遞迴解法,下面是一個遞迴解法:

1

class

solution

8if (phead2 ==null)

11if (phead1->val < phead2->val) else18}

19 };