파이문

148. Sort List 본문

문제 풀이/leetcode

148. Sort List

민Z 2020. 6. 30. 22:50
728x90

문제 설명

링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다.

솔루션

꼼수

가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다.

참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다.

아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다.

하지만 이러면 constant space complexity 를 만족할 수가 없다.

두뇌 풀가동

merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다.


이는 tortoise-hare 랑 비슷한데, fast 노드는 두칸씩 가고 slow 노드는 한칸씩 간다. fast 가 끝에 다다르면 slow 는 전체 링크드 리스트의 중간 노드를 가리키고 있을 것이다.

 

그럼 head ~ slow, slow ~ 어떤 노드 로 나누면 된다, 이를 각각 명칭을 알기 쉽게 변경하자면 start ~ middle, middle ~ end 이다.

 

다만 배열과 다르게 링크드 리스트는 middle 노드의 다음 번째 리스트가 쭉 이어져있기 때문에 그냥 돌리면 같은 것들을 계속 확인하게 된다.
말이 조금 어려워서 다시 정리하자면 아래와 같다.

3 -> 1 -> 2 -> 4

위와 같은 링크드 리스트에서 divide 가 이루어지면 3 -> 1, 2 -> 4 로 딱 나누어 떨어져야 하는데, 실제로 첫번쨰 리스트는 3 -> 1 -> (2 -> 4) 이렇게 되어 있다는 것이다.


이미 2 -> 4 는 나누어져서 다른 곳에서 어쩌고 저쩌고 할텐데, 이러면 cycle 이 되서 값이 제대로 나오지 않는다.

 

이를 위해 start -> middle 에서 middle 의 다음 리스트를 잘라주는 작업을 한다. 이렇게 모든 리스트를 잘라주었다면, 다음은 merge 작업을 진행해준다.

 

merge 작업은 두개의 노드의 값을 비교하는데, 각각을 left, right 라고 한다면 rightleft 보다 작으면 두개를 서로 바꿔준다. 서로 바꿔주는 작업도 역시 글은 어려우니 그림으로 보자.


아래와 같이 링크드 리스트가 있다고 할 때, 현재 leftright 가 아래와 같다고 해보자

left
1 -> 3

right
2 -> 5

(노드 개수가 2인 이유는 이미 divide 가 되었기 때문이고, merge 의 첫 과정이라고 생각하기 위해서이다.)

left 의 값이 1이고 right 의 값이 2 이다. 이는 정렬 되어 있으므로 leftnext 로 이동해주자

left
3

right
2 -> 5

여기서는 정렬 되어 있지 않는다. 이럴 경우 rightnext 와 비교한다.

left
3

right
5

left 보다 right 가 크니까 이대로 merge 한다. 그러면 3 -> 5 가 된다. 이제 거꾸로 가면 된다. 값이 작은 쪽으로 next 하여 비교 하였기 때문에 순서대로 right.nextleft.next 로 올라가면서 붙여주면 된다. 정리하면 이렇게 될 것이다.

(1)
left
1 -> 3
right
2 -> 5

(2)
left.next 로 이동

left
3
right
2 -> 5

(3)
right.next 로 이동

left
3
right
5

(4)
merge
3 -> 5

(5)
2 -> 3 -> 5 (right: 2, back, right.next 로 붙여준다.)
(6)
1 -> 2 -> 3 -> 5 (left: 1, back, left.next 로 붙여준다.)

전체 코드로 보면 아래와 같다.

class Solution:

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

        if head is None or head.next is None:
            return head

        middle = head
        fast = head.next
        slow = head.next

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            middle = middle.next

        middle.next = None

        node1 = self.sortList(head)
        node2 = self.sortList(slow)

        return self.merge(node1, node2)

    def merge(self, left, right):

        print(left, right)

        if left is None:
            return right

        if right is None:
            return left

        if left.val < right.val:
            left.next = self.merge(left.next, right)
            return left
        else:
            right.next = self.merge(left, right.next)
            return right

 

'문제 풀이 > leetcode' 카테고리의 다른 글

706. Design HashMap  (3) 2020.06.29
207. Course Schedule  (0) 2019.08.18
3. Longest Substring Without Repeating Characters  (0) 2019.07.08
2. Add Two Numbers  (0) 2019.06.16
518. Coin Change 2  (0) 2017.04.09
Comments