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
  1. BlogIcon 무료 영화
    2019.04.05 00:50

    잘보고 가욤 ^^