Katkat
Back

Merge Two Sorted Lists

Two SigmaData Scientist · Technical Screen
HardData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked list pointers to merge two sorted sequences efficiently without allocating extra space for new nodes.

Merge Two Sorted Linked Lists

You are given the heads of two sorted linked lists, list1 and list2.

Merge the two lists into one single sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Definition for singly-linked list node:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Function Signature:

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100.
  • Both list1 and list2 are sorted in non-decreasing order.

Examples:

Example 1: Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2: Input: list1 = [], list2 = [0] Output: [0]

Edge Cases:

  • One or both lists are empty.
  • Lists have different lengths.
  • All elements in one list are smaller than the smallest element in the other.

Hints

Hint 1

Consider using a 'dummy' head node to simplify the logic of handling the start of the merged list.

Hint 2

Maintain a 'current' pointer that tracks the last node appended to the merged list and compare the heads of the remaining parts of list1 and list2.

Hint 3

Once one list is exhausted, you can simply point the current node's next pointer to the remaining portion of the other list.

Follow-up questions

  • How would you modify your solution to merge K sorted linked lists instead of just two?
  • Can you implement this solution recursively, and what is the space complexity if you do?
  • If the lists were very large and stored on disk, how would you approach this problem to minimize memory usage?