Katkat
Back

Merge Two Sorted Singly Linked Lists

NetappSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to manipulate pointers in a singly linked list to perform an in-place merge of two sorted lists.

Merge Two Sorted Linked Lists

Given the heads of two non-decreasingly sorted singly linked lists, l1 and l2, merge them into a single sorted list. The operation should be performed by relinking the existing nodes, meaning you must not create new nodes for the output list. If the values of two nodes from l1 and l2 are equal, prioritize the node from l1.

Function Signature

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:

Constraints

  • The number of nodes in each list is in the range [0, 50].
  • Node values are integers between -100 and 100.
  • Both input lists are sorted in non-decreasing order.

Examples

Example 1: Input: l1 = [1, 2, 4], l2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] Explanation: The merged list is formed by alternating nodes: 1 (from l1), 1 (from l2), 2 (from l1), 3 (from l2), 4 (from l1), 4 (from l2).

Example 2: Input: l1 = [], l2 = [0] Output: [0]

Edge Cases

  • Empty lists (None).
  • Lists of unequal length.
  • Lists containing duplicate values.

Hints

Hint 1

Use a dummy head node to simplify the logic of attaching nodes to the new merged list.

Hint 2

Maintain a 'current' pointer to track the tail of the merged list as you traverse l1 and l2 simultaneously.

Hint 3

After one list is exhausted, simply point the remaining 'current' next pointer to the head of the non-empty list.

Follow-up questions

  • How would your approach change if you were required to perform the merge recursively instead of iteratively?
  • What is the time and space complexity of your solution?
  • How would you modify the algorithm if the lists were sorted in descending order instead of ascending?