Katkat
Back

Merge two sorted linked 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 structures in-place, focusing on space optimization and handling edge cases.

Problem Description

Given the heads of two singly-linked lists, list1 and list2, merge them into a single sorted list. The list should be made by splicing together the nodes of the first two lists. You must return the head of the merged linked list. You should aim for an in-place solution with O(1) extra space.

Definition for singly-linked list node

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

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both lists 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]

Implementation

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Write your solution here

Hints

Hint 1

Consider using a 'dummy' node to simplify the head management of the merged list.

Hint 2

Maintain a 'current' pointer to track the tail of the newly merged list as you iterate.

Hint 3

Once one list is exhausted, simply point the remaining 'current' next to the non-empty list.

Follow-up questions

  • How would your approach change if you needed to merge k sorted linked lists instead of two?
  • Can you solve this problem recursively, and what are the space complexity trade-offs compared to the iterative approach?
  • What modifications are needed if the lists were sorted in descending order instead of ascending?