[leetcode - 148. Sort List] java

문제 설명

1. 지금 값, 다음 노드가 들어있는 노드가 있다.

2. 이거 정렬하면 된다.

 

풀이 과정 

1. 분할 정복, 진짜 오래 헤맸고 혼자 못풀어서 해설을 보고 풀었다. 뭔가 알고리즘 실력에 점점 자신이 없어진다...

2. 결국은 이것도 반으로 나눠서 이거를 정렬해주면 되는 문제이다.

3. 반으로 나누기 : 보법이 다른 두개를 두고(한칸씩, 두칸씩) 두칸씩 가는 친구가 마지막까지 가면 한칸씩 가는 친구는 중간값이 된다.

4. 그리고 위의 (3) 과정에서 얻은 반에서 다음꺼로 가지 못하게 이동을 끊어버림

5. 구해진 반반을 계속 반복하면서 구하고

6. (5)의 과정에서 구해진 애를 크기 비교해서 node 를 구해주고

7. (6)으로 구한 애를 다시 (5)로 return 한 뒤 그거를 다시 (6) 해주는걸 반복하면 분할 - 정복 완료

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sortAndMerge(head); 
    }

    // 분할정복 시작
    private ListNode sortAndMerge(ListNode head) {
        if (head != null && head.next != null) { // 지금 head 가 마지막인지 파악을 위함. 분할과정의 마지막이면 걍 사용하면 된다.
            ListNode end = findMid(head); // 중간값 구해서
            ListNode start2 = end.next; // 중간값 다음부터 구하는 분할을 찾고
            end.next = null; // 이전 분할에서(중간값 이전까지 찾는것) 뒤에를 찾지 못하게 연결 끊기
            
            ListNode leftMerge = sortAndMerge(head); // 앞에 분할정복 시작
            ListNode rightMerge = sortAndMerge(start2); // 뒤에 분할정복 시작

            return merge(leftMerge, rightMerge); // 머지하는 부분
        }

        return head;
    }

    private ListNode merge(ListNode start, ListNode end) {
        // 비교대상 없으면 있는거 넣어주기
        if(start == null) return end; 
        if(end == null) return start;

        // 최초의 더미노드, 이거 다음부터가 진짜 답이다.
        ListNode dumy = new ListNode(-1);
        ListNode curr = dumy; // 뒤에 while 부터 next 가 생길것이다. 그 next 부터가 실질 답이 된다고 보면 됨.

        while(start != null && end != null) {
            if(start.val <= end.val) { // 정렬 적용. 왼쪽이 더 작으면 그걸 넣어주고 갱신하면 되낟.
                curr.next = start;
                start = start.next;
            } else {
                curr.next = end;
                end = end.next;
            }
            curr = curr.next; // 갱신된 그 값을 넣어주고 다음꺼를 구해주기 위해 shift
        }

        // 정렬된 상태의 start / end 를 통해 구해주는거라 앞의 while이 끝나면 그 뒤에는 정렬된 start / end 가 남는다.
        if(start != null) curr.next = start;
        else if(end != null) curr.next = end;

        return dumy.next;
    }

    private ListNode findMid(ListNode head) {
        // 한칸씩 가는거, 두칸씩 가는거 하나씩 두고 두칸씩 가는게 마지막에 도달하면 한칸씩 가는게 중간값이 된다.
        if (head == null) {
            return null;
        }
        ListNode oneStep = head;
        ListNode twoStep = head;

        while(twoStep.next != null && twoStep.next.next != null) {
            oneStep = oneStep.next;
            twoStep = twoStep.next.next;
        }

        return oneStep;
    }
}

 

이거는 나중에 다시 풀어봐야 하는 문제라고 생각한다.

지금은 풀이를 봐서 기억하지만 분명 나중에는 못풀것같음ㅇㅇ