LeetCode 148. Sort List

Description

https://leetcode.com/problems/shuffle-the-array/

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

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

Output: [1,2,3,4]

Example 2:

Output: [-1,0,3,4,5]

Example 3:

Output: []

Constraints:

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

Explanation

Use merge sort and use a find middle helper function.

Python Solution

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

return slow

def merge(self, l1, l2):
dummy = ListNode(0)
l3 = dummy

while l1 and l2:
if l1.val <= l2.val:
l3.next = l1
l1 = l1.next
else:
l3.next = l2
l2 = l2.next

l3 = l3.next

if l1:
l3.next = l1

if l2:
l3.next = l2

return dummy.next