Sort List Leetcode Solution
In this tutorial, we are going to solve a leetcode problem, Sort List in python.
Task:
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range [0, 5 * 104].
- -105 <= Node.val <= 105
Solution:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
lst = []
if head is None:
return None
cur = head
while cur != None:
lst.append(cur.val)
cur = cur.next
return self.ll(sorted(lst))
def ll(self, lst):
head = ListNode(lst[0])
cur = head
for i in range(1,len(lst)):
cur.next = ListNode(lst[i])
cur = cur.next
return head
Steps:
step1: In this problem, we are going to approach this by storing all the nodes values in a list and then making a function to make a linked list while taking the list as a parameter.
step2: First, we added a base case i.e. if the head is None then we return None.
step3: Then, we go through the linked list and append the node values into our list lst.
step4: Now, we make a function named ll which takes list as a parameter and converts it into a linked list and returns head.
step5: Then, we call the function ll on sorted lst and returns the head of the list as our answer.
