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 existing nodes given to us.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 8.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Смотрите видео Merge 2 Sorted Lists - A Fundamental Merge Sort Subroutine ("Merge Two Sorted Lists" on LeetCode) онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Back To Back SWE 24 Январь 2019, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 66,009 раз и оно понравилось 2.1 тысяч людям.