【問題描述】[簡單]

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。 示例：輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4

【解答思路】

1. 非遞歸

時間復雜度：O(N) 空間復雜度：O(N)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {//新建節點ListNode list = new ListNode(0);ListNode l =list;while(l1!= null && l2!= null){if(l1.val <= l2.val){l.next =l1 ;l1 = l1.next;l = l.next;}else {l.next = l2;l2 = l2.next;l =l.next;}}//某一條鏈表遍歷完畢if(l1 == null) {l.next =l2;}else {l.next =l1;}return list.next;}

2.遞歸

遞歸就是程序內部維護了一個棧。這個題就是每次都把最小值壓入棧，最后出棧的時候，將所有數連在一起就可以了。說白了，就是用一個棧維護了順序。最后的連接，當然是小的連小的，所以l1 小，就連到 l1,l2 小就連到 l2，最后先返回的，就是最小的頭結點

時間復雜度：O(N+M) 空間復雜度：O(1)
N M 分別為l1，l2兩者的長度

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) {return l2;}if(l2 == null) {return l1;}if(l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}作者：guanpengchn

圖解鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/hua-jie-suan-fa-21-he-bing-liang-ge-you-xu-lian-bi/

【總結】

1.遞歸 棧

2.鏈表畫圖理解

總結

以上是生活随笔為你收集整理的[剑指offer]面试题第[25]题[Leedcode][JAVA][第21题][合并两个有序链表]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。