Terrible LeetCode in Kotlin: #148 Sort List

42 Просмотры

  • Спасибо! Поделитесь с друзьями!

    Вам не понравилось видео. Спасибо за то что поделились своим мнением!

admin
Издатель
Another day, another LeetCode question (for now). Today, I'm running through #148 Sort List. The problem provides the head of a linked list and expects the head of the linked list, with the elements sorted.

At first glance, the problem seemed pretty benign, but as I dove deeper into it, I realized how complicated it could be if we used index-based sorting algorithms like Quicksort, or even Selection Sort. I couldn't figure out the exact sorting algorithm within the 30 minutes allotted, and took a peek at the solution.

The solution used merge sort. This in retrospect makes sense as that sorting algorithm is relatively index-agnostic, instead relying on divide and conquer to build up the final solution. The algorithm at a high level is pretty much the same, taking each half and then splitting until you arrive at 1 item, with the difference this time being that you have to use the 2 pointer traversal to find the middle of the list, and then split up (setting .next to null) the lists yourself.

I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.

Current Grind:
- Grind75 list, 22 weeks/16 hours per week, [108/169]
(https://www.techinterviewhandbook.org/grind75)

Chapters:
00:00 - Problem discussion
05:44 - Coding Begins (Attempt at QuickSort)
30:37 - Solution Discussion (Mergesort)
Категория
Язык программирования Kotlin
Комментариев нет.