148. Sort List Leetcode Solution

Sort List Leetcode Problem :

Given the head of a linked list, return the list after sorting it in ascending order.

jump game leetcode

Sort List Leetcode Solution :

Constraints :

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

Example 1:

  • Input: head = [-1,5,3,4,0]
  • Output: [-1,0,3,4,5]

Example 2:

  • Input: head = []
  • Output: []

Approach :

  • We want to sort a linked list, then we may able to use any of the sorting algorithm and then apply on it.
  • We will use merge sort here, because I find it easy to implement in linked list.
  • Whole implementation totally based on the merge sort, so i strongly suggest you to read a article on the merge sort.
    Some basic thing that we will do in applying merge sort on our linked list are-
  • We divide our linked liist into two equal parts until when only one element is left.
  • After that we start merge them on the basis of value.
  • Now, if we divide them into two equal parts then then how we will find mid in linked list.
  • We find mid of linked list using tortise and hare method or say using fast and slow pointer.
  • See commented code for more explanation.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription