21. Merge Two Sorted Lists
2304 ワード
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Original Solution)
Memory Usage: 38.1 MB
Some points to improve on) Instead of initializing the root, create a dummy and return root.next Use the ?: operator! Fixed Solution)
Memory Usage: 37.8 MB, less than 99.78% of Java online submissions for Merge Two Sorted Lists.
Another solution I thought was worth noting
Original Solution)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode root;
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
root = l1;
l1 = l1.next;
} else {
root = l2;
l2 = l2.next;
}
ListNode cur = root;
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;
}
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
return root;
}
Runtime: 1 msMemory Usage: 38.1 MB
Some points to improve on)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode root = new ListNode(0);
ListNode cur = root;
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 ? l2 : l1;
return root.next;
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.Memory Usage: 37.8 MB, less than 99.78% of Java online submissions for Merge Two Sorted Lists.
Another solution I thought was worth noting
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;
}
}
Reference
この問題について(21. Merge Two Sorted Lists), 我々は、より多くの情報をここで見つけました https://velog.io/@jwade/21.-Merge-Two-Sorted-Listsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol