Problem Overview

We are given the heads of two singly linked lists. Both the linked lists are sorted in ascending order.

Our goal is to merge the two lists into one sorted list and return the head.

Leetcode - Linked List Cycle

Example

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

Brute Force

Intuition

  • We can simply traverse each list and push all values into a vector.
  • Then we sort the vector.
  • While iterating through the vector, we create a new linked list.

Code

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        vector<int> values;

        while (list1) {
            values.push_back(list1->val);
            list1 = list1->next;
        }

        while (list2) {
            values.push_back(list2->val);
            list2 = list2->next;
        }

        sort(values.begin(), values.end());

        ListNode dummy(0);
        ListNode* tail = &dummy;

        for (int val : values) {
            tail->next = new ListNode(val);
            tail = tail->next;
        }

        return dummy.next;
    }
};

Why This Fails

  • The lists were already sorted, and we are not taking advantage of that.
  • It uses extra memory.
  • Sorting adds unnecessary overhead.

Time and Space Complexity

  • Time: O(n log n)
  • Space: O(n)

Optimal Solution

Instead of collecting all values, we directly compare nodes from both lists and attach the smaller one.

Edge Case Handling If node remain in the one of the list we can directly attack to the end.

Code

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        ListNode dummy(0);
        ListNode* curr = &dummy;

        while (list1 && list2) {
            if (list1->val <= list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }

        curr->next = list1 ? list1 : list2;

        return dummy.next;
    }
};

Time and Space Complexity

  • Time: O(n)
  • Space: O(1)

Final Takeaways

  • If the lists are already sorted, use that property.
  • Compare nodes directly instead of collecting and sorting.
  • Handle the edge case where one list still has remaining nodes.
  • Dummy node pattern makes pointer handling clean.