Merge 2 Sorted Lists - A Fundamental Merge Sort Subroutine ("Merge Two Sorted Lists" on LeetCode)

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: Given two lists that are sorted, merge them into a single sorted sequence as efficiently as possible. The key with linked list problems is pointers. Most of what we will do will be O(n) time and O(1) space. It is all about hardwiring things together and moving pointers around, have a strong understanding of techniques to advance, stash, and move references around. Approach 1 (Brute Force) Append the lists together and then sort the lists. The best we can do with this is O( n * log(n) ) because we will only know the total ordering property of the lists which lets us use (Mergesort or Quicksort, etc.) Approach 2 (Use Pointers And Rewire Lists) Huge tip. When building a new list while doing linked list problems dummy heads are your best friend. They prevent you from having to do null checks on a list and you can immediately append to the .next value through a pointer to it with no fear of a null pointer exception. We just keep: 1.) a pointer to the last item in the new list we are building 2.) a pointer into the first list 3.) a pointer into the second list We then do pair comparisons and advance accordingly. Complexities Time: O( m + n ) Let n be the length of list 1. Let m be the length of list 2. This is the worst case. We will be traversing the whole length of the lists in the case where they are nearly similar in length and value comparison results (aka we don't exhaust a list early before another). Best case is O( min( m, n ) ) because we will only traverse as far as we need to exhaust the shorter of the lists, then we just append the rest of the other onto the result since it will all be greater than the exhausted list by default. Space: O( 1 ) We are only working with pointers. We are using the existin