FastPrepMerge Two Descending Linked Lists

Merge Two Descending Linked Lists

Microsoft logoMicrosoft● EasyINTERNONSITE INTERVIEW
Learn

Problem statement

Given the heads of two singly linked lists listA and listB, each sorted in nonincreasing order, merge their nodes into one linked list that is also sorted in nonincreasing order.

Preserve every node value, including duplicates. Either input list may be empty.

Function

mergeDescendingLists(listA: ListNode, listB: ListNode) → ListNode

Examples

Example 1

listA = [9,7,3]listB = [10,8,7,1]return = [10,9,8,7,7,3,1]

At each step, append the larger current head. Both nodes with value 7 remain in the merged list.

Example 2

listA = []listB = [5,5,2]return = [5,5,2]

When one input is empty, the other list is already the complete descending result.

Example 3

listA = [4,2]listB = [3]return = [4,3,2]

The head 4 is followed by 3, then the remaining node 2.

Constraints

  • The two lists contain at most 100000 nodes in total.
  • Every node value is a signed 32-bit integer.
  • Each input list is sorted in nonincreasing order.

More Microsoft problems

See Microsoft hiring insights
/** Definition for singly-linked list.
 * class ListNode { int val; ListNode next; }
 */
public ListNode mergeDescendingLists(ListNode listA, ListNode listB) {
    // Write your code here.
}
listA[9,7,3]
listB[10,8,7,1]
expected[10,9,8,7,7,3,1]
Checking account…