🎉 Yay! DSA-30 is now live!
Day 3 - Linked Lists
Practice Questions
Merge Two Sorted Lists

Merge Two Sorted Lists

Description

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

Merge the two lists in a one 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.

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.

Test Cases

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

  • Input: list1 = [], list2 = [0]
    Output: [0]

Code

Approach 1: Iterative

Explanation

  1. Create a dummy node and a current node pointing to it.
  2. While both lists are not empty, compare the values of the nodes and add the smaller one to the current node.
  3. If one of the lists is empty, add the other list to the current node.
  4. Return the next node of the dummy node.

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)
Approach 2: Recursive

Explanation

  1. If one of the lists is empty, return the other list.
  2. If the value of the first node of the first list is smaller than the value of the first node of the second list, add the first node of the first list to the result and call the function again with the next node of the first list and the second list.
  3. If the value of the first node of the first list is greater than the value of the first node of the second list, add the first node of the second list to the result and call the function again with the first list and the next node of the second list.
  4. Return the result.

Analysis

  • Time Complexity: ``
  • Space Complexity: ``
Remove Duplicates from Sorted ListMultiply Two Numbers Represented as Linked Lists