Combine Two Sorted Lists | Dataford Interview Questions

Your question is Combine Two Sorted Lists. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

PlayStation Network services may maintain sorted linked lists of records, such as queued content identifiers or ordered activity entries. Given two linked lists whose values are sorted in non-decreasing order, merge them into one sorted linked list.

Reuse the existing nodes rather than creating a new node for every value. Return the head of the merged list. The input lists may be empty.

Formal Specification

Implement merge_two_lists(list1, list2).

list1 and list2 are either None or references to the heads of singly linked lists.
Each node has an integer val field and a next field containing another node or None.
Both lists are sorted in non-decreasing order.
Return a node reference to the head of the merged sorted list.
The test harness represents linked lists as arrays for input and expected output. For example, [1, 4] represents 1 -> 4 -> None.

Constraints

0 <= len(list1), len(list2) <= 10^4
-10^9 <= node.val <= 10^9
Each input list is sorted in non-decreasing order
The lists do not contain cycles

Function Signature

def merge_two_lists(list1, list2):