Skip to main content

Leetcode 21: Merge Two Sorted Lists

 

1. Problem Statement (Simple Explanation):


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

You must merge them into a single sorted linked list by reusing and splicing together the existing nodes (no need to create new nodes for values), and return the head of the merged list.

  • Both lists are sorted in non-decreasing order.

  • Either list may be empty.


2. Examples:


Example 1:


Input:

list1 = [1,2,4]

list2 = [1,3,4]

Merged list:

  • Compare 1 and 1 → pick either, say from list1 → [1]

  • Next compare 2 and 1 → pick 1 from list2 → [1,1]

  • Compare 2 and 3 → pick 2 → [1,1,2]

  • Compare 4 and 3 → pick 3 → [1,1,2,3]

  • Compare 4 and 4 → pick either 4 → then append remaining 4.

Output: [1,1,2,3,4,4]


Example 2:

Input:

list1 = []

list2 = []

Output: []

The merged list is empty.


Example 3:

Input:

list1 = []

list2 = [0]

Output: [0]


3. Approach – Iterative Merge with Dummy Head (Like Merge Step in Merge Sort):


This is similar to merging two sorted arrays, but using linked list nodes.


Intuition:


  • Use a dummy head node to simplify edge cases.

  • Maintain a pointer tail pointing to the last node of the merged list.

  • At each step, compare the current node values of list1 and list2:

    • Attach the node with the smaller value to tail.next.

    • Move that list’s pointer forward.

    • Move tail forward.

  • When one list is exhausted, attach the remaining part of the other list.

Since the input lists are already sorted, this produces a sorted merged list in one pass.


Algorithm (Step-by-Step):


  1. Create a dummy node: dummy = new ListNode(0).

  2. Initialize tail = dummy.

  3. While both list1 and list2 are not null:

    • if list1.val <= list2.val:

      • tail.next = list1

      • list1 = list1.next

    • else:

      • tail.next = list2

      • list2 = list2.next

    • Move tail = tail.next.

  4. After the loop, one of list1 or list2 is null:

    • Attach the non-null list:

      • tail.next = list1 if list1 not null

      • otherwise tail.next = list2

  5. Return dummy.next as the head of the merged list.


Pseudo-code:



Complexity:


Let:

  • m = length of list1

  • n = length of list2

Then:

  • Time: O(m + n) (each node visited once)

  • Space: O(1) extra (we just rearrange pointers)


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more