[알고리즘] LeetCode_148_Sort_List

Problem

Solve

정렬 알고리즘에는 여러가지가 있는데, 병합정렬 을 한 번 사용해보고자 한다.
먼저, 병합정렬이란? 일종은 분할 정복 알고리즘으로 배열을 나눌 수 있는 최대한으로 쪼갠 후에 더이상 쪼갤 수 없을 때 즉, 배열의 길이가 하나일 때를 기점으로 정렬을 다시 하면서 정복해나가는 느낌이다.

따라서, 이 문제에서는 head 라는 배열을 쪼개고, 최종적으로 병합된 배열을 반환해야 한다.
1. 분할하는 것은 배열의 길이의 1/2 로 나누어야 한다. 이를 위해 변수를 세 개 두어 두개의 배열로 나타낸다.
2. 나누어진 배열은 다시 재귀를 이용하여 최대한 나눈다.
3. base 기점은 그 자체가 null일 경우이거나, next 가 null 일 경우이다.
4. 2에서 최대한으로 나누었을 때 다시 합쳐지는 merge 과정을 거친다. 이때는 각각의 배열의 값을 비교하면서 붙여나간다.

class Solution {

	//Divide
    public ListNode sortList(ListNode head) {

        if(head == null || head.next == null) return head;
        
        ListNode prev = null;
        ListNode first = head;
        ListNode second = head;

        while(second != null && second.next != null){
            prev = first;
            first = first.next;
            second = second.next.next;
        }

        prev.next = null;

        
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(first);
        
        //최대한의 원소의 값이 하나일 때 l1, l2는 병합과정에 돌입
        return merge(l1,l2);
    }

	//Conquer
    ListNode merge(ListNode l1, ListNode l2){

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            } else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if(l1 != null){
            cur.next = l1;
        }
        if(l2 != null){
            cur.next = l2;
        }

        return dummy.next;

    }
}

⭐️ 어려웠던 점

분할 정복은 이론으로는 그림을 그리거나 시각적으로 보면 이해하기는 쉬웠다. 하지만, [] 배열이라면 쪼개는 과정에 있어서 길이의 반부터를 할당할 수는 있겠지만, 이 문제에서는 ListNode 연결리스트 라 반으로 쪼개는 방법 next 나 next.next 를 이해하기에 어려웠다. first 는 next를 이용해 리스트를 한칸씩 이동, second는 next.next를 이용해 두 칸 씩 이동하여 second가 기존 head의 끝에 도달하면 first는 head의 중간 지점을 가리키게 된다.

그리고 prev 변수가 굳이 필요할까? 라는 것에 의문을 가졌다. prev는 연결리스트를 반으로 나눌 때 first 포인터의 이전 노드를 기록하면서 첫번째 반의 끝을 나타내는 역할을 한다. 이를 이용해 첫번째 반의 끝을 나타내는 prev.next = null 로 설정하여 head와 first로 두 개의 독립적인 연결 리스트를 생성할 수 있는 것이다.

(prev의 필요성이 없는 것 같아 주석처리를 했더니,
Run Time Error 가 나왔다.)