[LeetCode][Python3] 148. Sort List

Problem :

https://leetcode.com/problems/sort-list/

My Solution :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def sortList(self, head: ListNode) -> ListNode:

if head and head.next:

prev = slow = fast = head

while fast and fast.next:

prev = slow

slow = slow.next

fast = fast.next.next

prev.next = None

left = self.sortList(head)

right = self.sortList(slow)

return self.merge(left, right)

return head

def merge(self, left, right):

current = dummy = ListNode(0)

while left and right:

if left.val < right.val:

current.next = left

left = left.next

else:

current.next = right

right = right.next

current = current.next

current.next = left or right

return dummy.next

Comment :

문제에서 O(nlogn) time and O(1) space 를 요구했기 때문에 병합정렬을 활용해 풀어야 한다. 나는 처음에 해당 조건을 무시하고 그냥 아래와 같이 내장 sorted를 활용하였다. 속도는 내장 sorted가 훨씬 빠르게 동작한다.

My Solution 2 :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def sortList(self, head: ListNode) -> ListNode:

if not head:

return head

nodes = []

while head:

nodes.append(head)

head = head.next

nodes = sorted(nodes, key=lambda x: x.val)

for i in range(len(nodes)-1):

nodes[i].next = nodes[i+1]

nodes[-1].next = None

return nodes[0]

그리고 val만 뽑아서 정렬한 다음 ListNode의 next를 재배치 하는 대신 val을 직접 수정하면 조금 더 빠르다.

My Solution 3 :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def sortList(self, head: ListNode) -> ListNode:

vals = []

curr = head

while curr:

vals.append(curr.val)

curr = curr.next

vals = sorted(vals)

i = 0

curr = head

while curr:

curr.val = vals[i]

i += 1

curr = curr.next

return head