1
package 递归.q21_合并两个有序链表.f1;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
package 递归.q21_合并两个有序链表.f1;
/**
* 插队法 - 遍历迭代 o(n)
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = new ListNode(Integer.MIN_VALUE);
head.next = l1;
ListNode pre = head;
while (l2 != null) {
ListNode t1 = pre.next;
ListNode t2 = l2.next;
while (l2.val > t1.val) {
if (t1.next == null) {
t1.next = l2;
return head.next;
} else {
pre = pre.next;
t1 = t1.next;
}
}
pre.next = l2;
l2.next = t1;
l2 = t2;
}
return head.next;
}
}
2
package 递归.q21_合并两个有序链表.f2;
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
package 递归.q21_合并两个有序链表.f2;
/**
* 递归(看成两个链表头部较小的一个与剩下元素的 merge 操作结果合并) o(n)
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}