##題目描述 輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則，
思路
遞回與非遞回，
時間復雜度O(m+n)，空間復雜度O(m+n)，
遞回代碼
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode curr = null;
if(list1.val < list2.val) {
curr = list1;
curr.next = Merge(list1.next, list2);
} else {
curr = list2;
curr.next = Merge(list1, list2.next);
}
return curr;
}
}
非遞回代碼
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode head = null;
ListNode curr = null;
if(list1.val < list2.val) {
head = list1;
list1 = list1.next;
} else {
head = list2;
list2 = list2.next;
}
curr = head;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
if(list1 != null) {
curr.next = list1;
}
if(list2 != null) {
curr.next = list2;
}
return head;
}
}
筆記
提交時遞回運行速度更快，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86930.html
標籤：其他
上一篇：反轉鏈表
下一篇：樹的子結構