Merge Two Sorted Lists
Leetcode #21 | Easy | Связный список | Два указателя
Идея
Создаем dummy, заводим два указателя. Идем пока кто-то не станет null. Если p1.val >= p2.val, то цепляем cur.next = p2 и двигаем p2 вместе с cur, иначе цепляем и двигаем p1 к cur. Когда кто-то стал null просто цепляем все, где не null. Возвращаем dummy.next
Big-O
- Время
O(N+M) - Память
O(1)
Код
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
else { cur.next = l2; l2 = l2.next; }
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}