EASY NC#36 Blind #42 Linked List
21. Merge Two Sorted Lists
📖 Problem
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into 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.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
💡 Approach
- → Use dummy head to simplify list construction
- → Compare nodes from both lists and add smaller to result
- → Append remaining nodes from the longer list
- → Time: O(m + n), Space: O(1) (excluding result)
🛠️ Hints & Pitfalls
Hints
- •Use dummy head to simplify list construction
- •Compare nodes from both lists and add smaller to result
- •Append remaining nodes from the longer list
Common Pitfalls
- •Time: O(m + n), Space: O(1) (excluding result)
🧪 Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
mergeTwoLists(arrayToList([1,2,4]), arrayToList([1,3,4])); Expected:
{"val":1,"next":{"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":4,"next":null}}}}}} Test Case 2
Not run Input:
mergeTwoLists(arrayToList([]), arrayToList([])); Expected:
null Test Case 3
Not run Input:
mergeTwoLists(arrayToList([]), arrayToList([0])); Expected:
{"val":0,"next":null} 📝 Code Editor
📤 Output