[python] leetcode 148. Sort List

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

Sort List - LeetCode

 

- task: 연결리스트 sort

- 제약조건: 시간복잡도 O(nlogn), 공간복잡도 O(1)

- 고려해야할 사항: 연결리스트로 주어진다는 점, 시간복잡도가 O(nlogn)이라는 점

 

- 접근방법

 1) 제약조건을 고려했을 때 안정적으로 O(nlogn)의 시간을 보장하는 병합정렬을 활용하자.

 2) 병합정렬은 중간 지점을 파악하는 게 중요한데 연결리스트는 중간 지점을 파악하기가 어렵다. -> Runner 기법을 사      용해서 중간지점을 파악하자.

 

- 어려웠던 점

 1) runner 기법을 통해 중간지점은 찾았는데, 분할 시에 왼쪽 리스트와 오른쪽 리스트를 구분해서 넘겨주는 방법을 생각을 못함.

-> 이 경우에는 mid라는 변수를 단순히 slow와 같은 곳을 가리키도록 하기보다는, 하나의 연결리스트로서 기능하도록 하는 것이 맞다.

2) 분할을 어떻게 할지 감이 안옴. (재귀를 사용해야 되는 건 알겠는데 정확히 어떤 식으로 해야할지에 대한 감이 잘 안왔다)

3) 분할까지는 생각을 했는데 어떤 식으로 정렬을 해야할지? merge하는 과정에서 어떤 식으로 붙여야할까에 대한 고민을 더 해봐야했음.

 

 

- 풀이

class Solution:
    def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:
        """
        비교 후 정렬하며 병합 (얘도 재귀호출)
        """
        if l1 and l2:
            if l1.val > l2.val:# swap 조건
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2) # 병합하는 부분

        return l1 or l2 # none이 아닌 걸 리턴하게 됨 (둘 다 none이 아닐 경우에는 l1이 먼저 리턴)

    def sortList(self, head: ListNode) -> ListNode:
        if not (head and head.next): # 재귀 종료 조건 (next도 체크 안해주면 med.next에서 Nonetype object has no attribute 'next' error 뜸)
            return head

        med, slow, fast = None, head, head

        while fast and fast.next: # 런너기법 사용 (분할지점 찾기 위함)
            med, slow, fast = slow, slow.next, fast.next.next

        med.next = None # 아예 head 노드가 가리키는 연결리스트 자체를 반쪽으로 쪼개버림
        # 뒷부분은 slow가 이미 가리키고 있기 때문에 상관이 없음

        l1 = self.sortList(head) # 앞부분
        l2 = self.sortList(slow) # 뒷부분

        return self.mergeTwoLists(l1, l2)