21. Merge Two Sorted Lists#

Code#

 1public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
 2  ListNode dummyHead = new ListNode();
 3  ListNode currentNode = dummyHead;
 4
 5  while (list1 != null && list2 != null) {
 6    if (list1.val <= list2.val) {
 7      currentNode.next = list1;
 8      list1 = list1.next;
 9    } else {
10      currentNode.next = list2;
11      list2 = list2.next;
12    }
13    currentNode = currentNode.next;
14  }
15
16  if (list1 != null) {
17    currentNode.next = list1;
18  } else {
19    currentNode.next = list2;
20  }
21
22  return dummyHead.next;
23}

Time Complexity

Space Complexity

\(\mathcal{O}(n)\)

\(\mathcal{O}(1)\)