-
Notifications
You must be signed in to change notification settings - Fork 326
/
58-1.py
32 lines (25 loc) · 865 Bytes
/
58-1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 두 정렬 리스트 병합
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val:
l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
def sortList(self, head: ListNode) -> ListNode:
if not (head and head.next):
return head
# 런너 기법 활용
half, slow, fast = None, head, head
while fast and fast.next:
half, slow, fast = slow, slow.next, fast.next.next
half.next = None
# 분할 재귀 호출
l1 = self.sortList(head)
l2 = self.sortList(slow)
return self.mergeTwoLists(l1, l2)