[Grind75-LeetCode] Merge Two Sorted Lists JAVA

반응형

728x90

[Grind75] Merge Two Sorted Lists - Easy

---

접근

• 구현

---

풀이

새로운 알고리즘 문제 사이트 풀이를 시작했다. 유명하다는 Leetcode의 문제를 75개의 주요 문제로 구성해 제공하는 사이트로 주차별로 문제를 나눠 풀 수 있게 도움을 준다. UI도 깔끔하고 프로그래머스의 상위호환 같은 환경을 제공해주는거 같다. 한 가지 아쉬운점은 아무래도 영어로 된 사이트이다 보니 문제 이해에 시간이 좀 걸리는 편이다. 처음 쉬움 단계의 문제를 몇 개 풀다가 느꼈는데 백준으로 치면 실버 저티어의 난이도는 되는게 아닌가 싶은 진짜 쉬움(?)이 아닌 상대적 쉬움 난이도인거 같다. 그렇다고 어려운건 아니지만 이게 쉬움이면 나중에 어려움 난이도는 어떤 문제들인가 싶다. 

 

그래서 이번 문제는 연결된 노드가 리스트처럼 주어진다. 노드 클래스 내 값을 나타내는 필드와 다음 노드를 가리키는 노드 필드가 존재하여 정렬된 상태의 연결된 리스트를 이루고 있고 주어지는 두 리스트를 순서에 맞게, 정렬된 상태로 병합하는 문제이다. 반환 타입이 문제에서 주어지는 ListNode 클래스이고 백준이나 프로그래머스에서 못 보던 느낌의 문제라 가져왔다.

/**
 * 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 클래스의 모습이다. 필드 값으로 int 값을 저장하는 val 그리고 연결된 다음 ListNode가 있다. 각 생성자도 선언되어 있다. 제출할 때는 저 코드는 구현할 필요 없이 요구하는 함수의 코드만 구현하면 된다. 

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode(0);
        ListNode current = result;

구현해야할 메서드로 두 개의 리스트 노드를 파라미터로 받게 된다. 풀이를 위해 두 리스트 노드를 선언해주었는데 두 리스트를 병합할 결과 리스트 노드와 병합하는 과정에 사용할 current 리스트 노드를 선언했다. result 리스트 노드는 val값이 0이고 next가 null인 상태로 선언되었는데 해당 단계의 result는 단순히 리스트 병합을 위한 초석 역할을 하는 단계로 실제 리스트는 result의 next부터 시작하여 쌓이게 된다. 그리고 current는 result를 참조하여 생성되었기 때문에 current는 result와 같은 값을 공유하게 되고 current는 result 리스트를 만드는 과정에 사용되고 result는 결과 출력을 위해 사용되는 것이다.

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

리스트를 병합하는 과정이다. 두 노드를 비교해 작은 값을 다음 노드로 추가하게 되는데 current를 사용하게 된다. current는 result와 같은 참조를 가지기 때문에 current를 사용해 포인터를 옮겨주며 result 리스트를 만들게 된다. 작은 값을 현재 result의 다음 노드로 연결한 뒤 current를 사용해 연결한 노드로 이동하여 다음 연결을 진행하게 된다.

result = 0번지
current = 0번지


if 문 list1 < list2 일 경우{
    current.next = list1 -> result.next = list1
}

current = current.next -> current = current.list1

1회 반복 후 
result = 0번지
current = 1번지

위 처럼 result의 경우 결과 출력을 위해 0번지를 유지하고 current의 포인터를 움직여 result 리스트를 만들어주는 것이다.

	if (list1 != null) {
            current.next = list1;
        } else if (list2 != null) {
            current.next = list2;
        }

        return result.next;

한쪽 리스트만 값이 남아있다면 추가해주고 결과로 result의 next인 병합 리스트 시작점을 반환해준다.

---

전체 코드

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode(0);
        ListNode current = result;

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

        if (list1 != null) {
            current.next = list1;
        } else if (list2 != null) {
            current.next = list2;
        }

        return result.next;
    }
}