[@ToString, Divide and Conquer] Leetcode 148. Sort List

https://leetcode.com/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150 

Sort List - LeetCode

https://github.com/fineman999/algorithm_java/issues/9

148. Sort List · Issue #9 · fineman999/algorithm_java

---

1. 서론

Node를 통해 오름차순으로 정렬하는 문제다.

분할과 병합을 통해 구현한다.

추가로 문자열 확인을 위해 @ToString을 오버라이딩하였다.

 

2. 알고리즘 내용

연결된 목록의 머리 부분을 지정하면 오름차순으로 정렬한 후 목록을 반환한다.

Example 1:

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

 

3. 알고리즘 내용

3.1 LisNode Class

/**
 * 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; }
 * }
 */

문제 주어진 ListNode Class이다.

테스트를 하기 위해 문제 예시를 바탕으로 테스트 케이스를 만들어보자.

 

class ListNodeTest {

    @Test
    @DisplayName("of(4, 2, 1, 3)을 통해 ListNode 4 -> 2 -> 1 -> 3을 생성할 수 있다.")
    void example() {
        ListNode head = ListNode.of(4, 2, 1, 3);
        assertThat(head.toString()).isEqualTo("4 -> 2 -> 1 -> 3");
    }

    @Test
    @DisplayName("of(-1, 5, 3, 4, 0)을 통해 ListNode -1 -> 5 -> 3 -> 4 -> 0을 생성할 수 있다.")
    void example2() {
        ListNode head = ListNode.of(-1, 5, 3, 4, 0);
        assertThat(head.toString()).isEqualTo("-1 -> 5 -> 3 -> 4 -> 0");
    }
}

ListNode.of(-1, 5, 3, 4, 0)를 통해 ListNode 연결리스트를 작성하고 결과값은 "-1 -> 5 -> 3 -> 4 -> 0" 나오게 작성하였다.

이제 프로덕션 코드를 작성해보자

 

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; }

    public static ListNode of(int... values) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }
        return dummy.next;
    }

    /**
     * ListNode를 문자열 표현을 반환한다.
     * 이 문자열은 next를 통해 값 -> 다음 값 -> 다음 값 -> ...  형태로 반환한다.
     * next가 null이면 값만 반환한다.
     */
    @Override
    public String toString() {
        if (next == null) return String.valueOf(val);

        return new StringJoiner(" -> ", "", "")
                .add(String.valueOf(val))
                .add(next.toString())
                .toString();
    }
}

이팩티브 자바에서 아이템 12. toString을 항상 재정의하라.에서는 toString은 간결하면서 사람이 읽기 쉬운 형태의 유익한 정보를 반환해야 한다고 한다.

toString을 재정의하지 않으면 org.leetcode.sortlist.ListNode@7dc19a70같은 형태로 출력 하게 된다. @기준으로 왼쪽은 클래스 이름, 오른쪽은 16진수로 표시한 해시코드이다.(클래스이름@ 16진수로 표시한 해시 코드)

또한 포맷을 문서에 명시하는 것이 좋다.

 

테스트 성공

이제 정렬을 만들어 보자.

 

3.2 알고리즘 풀이 Solution

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode middle = getMiddle(head);
        ListNode nextOfMiddle = middle.next;
        middle.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(nextOfMiddle);
        return merge(left, right);
    }

    private ListNode getMiddle(ListNode head) {
        if (head == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return slow;
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                tail.next = left;
                left = left.next;
            }
            else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        if (left != null) tail.next = left;
        if (right != null) tail.next = right;
        return dummy.next;
    }
}

Solution 클래스에 외부에서 사용할 수 있는 SortList 메서드가 있고, SortList 메서드가 사용하고 있는 merge와 getMiddle private 메서드가 있다.

먼저 getMiddle를 살펴보자

 

getMiddle

• 주어진 연결 리스트의 중간 노드를 찾는 역할을 한다.
• 이전에 토끼와 거북이 알고리즘과 비슷하다.
• fast 노드는 한 번에 두 노드씩 이동하고, slow 노드는 한 번에 한 노드 씩 이동
• fast 노드가 null에 도착하면 slow 노드는 중간 노드에 위치하게 된다.

 

merge

• 두 개의 정렬된 연결된 연결 리스트 left와 right를 병합하여 하나의 정렬된 리스트를 생성하고 반환한다.
• dummy 노드를 생로 생성하고 tail 노드를 통해 노드를 추가한다.
• left와 right 노드를 비교하여 작은 값을 tail 노드의 다음 노드에 추가하고 다음 노드로 이동하낟.
• left와 right 중 남는 노드가 있을경우 tail 노드의 다음 노드에 추가한다.
• 최종적으로 dummy.next를 반환하여 정렬된 연결 리스트를 반환한다.

 

sortList

• 주어진 연결 리스트 head를 정렬하게 된다.
• getMiddle 메서드를 통해 중간으로 나누고 left, right로 분리한다.
• 나눈 두 개의 작은 리스트를 각각 재귀적으로 정렬하고, 그 결과를 merge 메서드를 통해 병합한다.
• 병합한 리스트를 반환한다.

 

3.3 테스트 결과

테스트 결과

Leetcode 결과

테스트가 성공 한 것을 볼 수 있다.