[LeetCode] 148. Sort List - Java[자바]

링크

문제

Linked List의 head가 주어지면 오름차순으로 정렬한 후 목록을 반환합니다.

풀이

떠올린 풀이는 List 만들어서 Linked List의 노드들 값 담고, Collections.sort() 메서드를 이용해서 정렬후 새로 LinkedList 만들어서 return하려고 했으나.. 이건 원하는 풀이가 아닌 것을 알기에 접어뒀다.

그 이후에는 LinkedList의 여러 정렬 방법을 이용하면 되겠다 싶었다.

구현이 복잡하더라도, merge sort를 익혀두는 편이 제일 좋겠다 싶었다.

merge sort를 간단히 정리해보자.

1. 정렬하려는 대상을 원소가 단 한개 있는 unit 단위까지 쪼갠다. 이유는 원소가 단 1개라면, 정렬이 되었다고 간주하기 때문이다.
2. 위에서 쪼갠 sub 배열 or 리스트를 반복적으로 정렬하며 merge 한다.

의사 코드를 생각해보면,

위에서 언급한 1에 필요한 중간 원소를 찾는 메서드, 쪼개진 녀석들을 정렬하는 메서드, 2에 필요한 merge 메서드 총 3개의 큰 부분으로 나눌 수 있다.

class Solution {  
  
    public ListNode sortList(ListNode head) {  
        if (head == null || head.next == null) {  
            return head;  
        }  
        ListNode mid = getMid(head);  
        ListNode left = sortList(head);  
        ListNode right = sortList(mid);  
        return merge(left, right);  
    }  
  
    private ListNode merge(ListNode list1, ListNode list2) {  
        // 빈 노드 생성  
        ListNode dummy = new ListNode(-1);  
        ListNode current = dummy;  
  
        while (list1 != null && list2 != null) {  
            if (list1.val <= list2.val) {  
                current.next = list1;  
                list1 = list1.next;  
            } else {  
                current.next = list2;  
                list2 = list2.next;  
            }  
            current = current.next;  
        }  
  
        // 위의 while문이 끝나고도 ListNode가 남아있다면, 나머지를 뒤로 붙임  
        if (list1 != null) {  
            current.next = list1;  
        } else {  
            current.next = list2;  
        }  
        return dummy.next;  
    }  
  
    public ListNode getMid(ListNode head) {  
        ListNode slow = head;  
        ListNode fast = head.next;  
  
        while (fast != null && fast.next != null) {  
            slow = slow.next;  
            fast = fast.next.next;  
        }  
        ListNode mid = slow.next;  
        slow.next = null;  
        return mid;  
    }  
}