Sort List

문제

연결리스트의 선두인 head가 주어지면 오름차순으로 정렬한 후 리스트를 반환하세요.

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Input: head = []
Output: []

접근 방향

리스트 노드를 순회하면서 배열에 각 노드 값을 저장한 뒤 해당 배열에 저장된 노드 값을 선택 정렬로 순회하면서 정렬된 값을 차례로 노드로 만들어 더미 노드에 연결하여 리스트 노드의 헤더 노드를 반환하였지만 O(N ** N)의 시간 복잡도로 시간 초과가 발생하였다.

나의 풀이

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        l = []
        # 인수 head 연결 리스트 노드를 순회하면서 값을 l에 저장
        while head:
            l.append(head.val)
            head = head.next

        # 더미 노드 생성
        dummy = ListNode(0)
        cur = dummy

        # 포인터와 위치를 바꿀 대상 포인터(change_pointer) 0 할당
        pointer, change_pointer = 0, 0
        # 최솟값을 추출하기 위해 무한대 할당
        minimum = float('inf')

        # 포인터가 마지막 노드 값의 인덱스보다 작을 때까지 반복
        while pointer < len(l):
            for idx, num in enumerate(l[pointer:]):
                # minimum보다 num이 작을 경우 num을 minimum에 저장 후
                # change_pointer에 idx와 포인터를 더한 값을 할당
                # 최초 인덱스가 pointer부터 순회하도록 하였으므로 change_pointer에
                # idx와 pointer를 추가로 더해야 전체 리스트 인덱스에서 유효한 인덱스를 가리킨다.
                if minimum > num:
                    minimum = num
                    change_pointer = idx + pointer
            # 가장 작은 요소의 인덱스를 가르키는 change_pointer와 pointer 위치 변경
            l[pointer], l[change_pointer] = l[change_pointer], l[pointer]

            # 가장 작은 값을 가진 노드 순서대로 더미 노드에 연결
            cur.next = ListNode(l[pointer])
            cur = cur.next

            # 포인터 1 증가, minimum 초기화
            pointer += 1
            minimum = float('inf')

        return dummy.next

다른 사람의 풀이

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # head가 노드이거나 연결 리스트 노드가 아닌 경우 head 반환, 연결리스트 노드만 처리
        if not head or not head.next:
            return head

        # slow는 이전 노드, fast는 다음 노드
        slow = head
        fast = head.next

        # slow 포인터는 한 칸씩 이동, fast 포인터는 두 칸씩 이동
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # 중간 인덱스 저장
        mid = slow.next
        # 노드 연결리스트 끊기
        slow.next = None

        # 더 작은 연결 리스트로 계속해서 쪼개기
        left = self.sortList(head)
        right = self.sortList(mid)

        # 더미 노드 생성
        tmp = ref = ListNode(0)

        # 왼쪽과 오른쪽 연결 리스트가 존재한다면
        while(left and right):
            # 왼쪽 노드 값이 더 작다면
            if left.val < right.val:
                # 왼쪽 노드를 더미 노드 다음 노드에 연결
                tmp.next = left
                # left 연결리스트는 다음 노드로 이동
                left = left.next
            # 오른쪽 노드 값이 더 작다면
            else:
                # 오른쪽 노드를 더미 노드 다음 노드에 연결
                tmp.next = right
                # right 연결리스트 다음 노드로 이동
                right = right.next
            # 더미 노드 오른쪽 이동
            tmp = tmp.next

        # 마지막으로 남은 노드는 가장 큰 노드이므로 가장 마지막에 더미 노드와 연결
        tmp.next = left if left else right

        # 더미 노드 다음 노드 (헤드 노드 반환)
        return ref.next

위 코드는 평균 시간복잡도가 O(nlog(n))인 병합 정렬을 사용하였으며 포인터를 이동하면서 중간 인덱스 위치를 찾기 위해서 slow 포인터는 한 칸씩 이동하게 하고 fast 포인터는 두 칸씩 이동하게 하여 fast 포인터가 끝에 도달하여 탐색을 마쳤을 경우 slow 포인터가 중간에 위치한다는 점을 사용하였다.

# slow는 fast 포인터보다 한 칸 뒤에서 출발
1 -> 2 -> 3 -> 4 -> 5
-s  -f

# slow 포인터는 한 칸씩 이동, fast 포인터는 두 칸씩 이동
1 -> 2 -> 3 -> 4 -> 5
     -s       -f

# fast 포인터가 탐색을 마쳤을 때 slow 포인터는 중간에 위치
1 -> 2 -> 3 -> 4 -> 5
          -s  -f