刷题LeetCode21。合并两个有序链表

　　来源：力扣（LeetCode）
　　链接：https：leetcodecn。comproblemsmergetwosortedlists题目描述
　　将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。题目分析
　　提供两种方法：递归迭代代码实现publicclassHeBingList21｛publicstaticvoidmain（String〔〕args）｛HeBingList21fanZhuanList206newHeBingList21（）；ListNodeheadnewListNode（1，newListNode（2，newListNode（3，newListNode（4））））；ListNodehead2newListNode（1，newListNode（4，newListNode（6，newListNode（7））））；fanZhuanList206。mergeTwoLists（head，head2）；｝递归paraml1paraml2returnpublicListNodemergeTwoLists2（ListNodel1，ListNodel2）｛if（l1null）｛returnl2；｝if（l2null）｛returnl1；｝if（l1。vall2。val）｛l1。nextmergeTwoLists2（l1。next，l2）；returnl1；｝else｛l2。nextmergeTwoLists2（l1，l2。next）；returnl2；｝｝时间复杂度：O（nm），其中n和m分别为两个链表的长度。因为每次循环迭代中，l1和l2只有一个元素会被放进合并链表中，因此while循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为O（nm）。p空间复杂度：O（1）。我们只需要常数的空间存放若干变量。paraml1paraml2returnpublicListNodemergeTwoLists（ListNodel1，ListNodel2）｛if（l1nulll2null）｛returnnull；｝ListNoderesultnewListNode（1）；ListNodecurrresult；while（l1！nulll2！null）｛if（l1null）｛curr。nextl2；l2l2。next；｝elseif（l2null）｛curr。nextl1；l1l1。next；｝else｛if（l1。vall2。val）｛curr。nextl1；l1l1。next；｝else｛curr。nextl2；l2l2。next；｝｝currcurr。next；｝returnresult。next；｝｝
　　递归复杂度时间复杂度：O（nm），其中n和m分别为两个链表的长度。空间复杂度：O（nm）。迭代复杂度时间复杂度：O（nm）。因为每次循环迭代中，l1和l2只有一个元素会被放进合并链表中，因此while循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为O（nm）。空间复杂度：O（1）。
　　好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！