Problem: 21. 合并两个有序链表

💖 递归

思路

👨‍🏫 参考地址

$n,m$ 分别为 list1 和 list2 的元素个数
⏰ 时间复杂度: $O(n+m)$
🌎 空间复杂度: $O(n+m)$

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2){if (list1 == null)return list2;else if (list2 == null)return list1;else if (list1.val < list2.val){list1.next = mergeTwoLists(list1.next, list2);return list1;} else{list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}

💖 双指针

👨‍🏫 参考地址

⏰ 时间复杂度: $O(n+m)$
🌎 空间复杂度: $O(1)$

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dum = new ListNode(0), cur = dum;while (list1 != null && list2 != null) {if (list1.val < list2.val) {cur.next = list1;list1 = list1.next;}else {cur.next = list2;list2 = list2.next;}cur = cur.next;}cur.next = list1 != null ? list1 : list2;return dum.next;}
}