21. Merge Two Sorted Lists

Problem

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 

Solution

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { var head = new ListNode(0); var now = head; var p1 = l1; var p2 = l2; while (p1 || p2) { if (p1 === null || (p2 !== null && p2.val < p1.val)) { now.next = p2; p2 = p2.next; } else { now.next = p1; p1 = p1.next; } now = now.next; } return head.next; }; 

Explain:

nope.

Complexity:

• Time complexity : O(m+n).
• Space complexity : O(m+n).