[문제14][LeetCode] 21. 두 정렬 리스트의 병합

https://leetcode.com/problems/merge-two-sorted-lists/

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

 

Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

 

접근 방법

0. 문제 이해: 두 개의 정렬된 연결 리스트를 병합해 새로운 정렬된 리스트를 만들어 반환합니다.

✔ 생각해 볼 것: 

- 처음부터 두 리스트가 비어있을 경우 ➡ 빈 링크드리스트 반환

- 연산 중 한 리스트가 비게 될 경우 ➡ 다른 리스트의 원소를 링크드리스트에 삽입 후 반환

1. 시간복잡도: O(N)

2. 두 리스트를 큐에 각각 넣습니다. 

3. 두 리스트 중에 한 리스트가 빌 때까지 while문을 돌면서 원소 비교 후 링크드리스트에 삽입합니다.

 

코드 구현

실패 코드

/**
 * 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; }
 * }
 */
import java.util.*;
class Solution {
    public LinkedList<Integer> mergeTwoLists(ListNode list1, ListNode list2) {
        // 반환 할 링크드 리스트 선언
        LinkedList<Integer> linkedList = new LinkedList<>();

        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();

        ListNode current = list1;
        while (current != null) {
            q1.add(current.val);
            current = current.next;
        }

        current = list2;
        while(current != null) {
            q2.add(current.val);
            current = current.next;
        }

       	// 빈 리스트일 경우 처리
        if(q1.isEmpty() && q2.isEmpty()){
            return linkedList;
        }

        // 과정 중에 한 쪽이 빈 큐가 되면 상대 큐 -> linkedlist를 반환
        while (!(q1.isEmpty() || q2.isEmpty())){
            // 각 큐의 첫 원소 크기 비교 후 삽입
            if(q1.poll() < q2.poll()){
                linkedList.add(q1.poll());
                linkedList.add(q2.poll());
            }

            // 두 큐의 원소 크기를 비교해서 작은 것부터 삽입
            if(q1.poll() < q2.poll()){
                linkedList.add(q1.poll());
            }else {
                linkedList.add(q2.poll());
            }
        }
        return linkedList;
    }
}

 

원인

편의를 위해 반환 타입을 마음대로 수정했는데...  이 부분에서 에러가 났습니다. 마음대로 수정해도 되는 줄 알았던..

주어진 대로 다시 풀이해야겠습니다.

ListNode ➡ LinkedList<Integer>

 

그리고 peek() vs poll() 사용법 미숙이 있겠습니다.

 

해결 방법

✔ 더미 노드 사용하기

더미 노드는 연결리스트에서 head를 처리할 때 사용되는 기술로써 실제 데이터를 저장하진 않습니다. 연결 리스트의 head에 새로운 노드를 추가, 삭제, 변경될 때 사용되며 연산이 모두 끝나고는 실제 데이터가 있는 지점인 dummy.next를 반환합니다. (찐 연결 리스트의 head)

 

성공 코드

/**
 * 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 dummy = new ListNode(0);
        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;
        }

        // list1 또는 list2 중 하나가 먼저 끝났을 경우, 나머지 리스트 연결
        if (list1 != null) {
            current.next = list1;
        } else if (list2 != null) {
            current.next = list2;
        }

        // 더미 노드의 다음 노드를 반환
        return dummy.next;
    }
}

코드 최적화 뿌-듯

 

배우게 된 점

1. ListNode 순회 방법 

ListNode는 단일 노드로 결국에는 ListNode 타입의 연결 리스트를 순회해야 합니다. ListNode의 인스턴스에서 시작하여 .next 속성을 사용하여 연결 리스트를 순회해야 합니다.

 public LinkedList<Integer> mergeTwoLists(ListNode list1, ListNode list2) {
    Queue<Integer> q1 = new ArrayDeque<>();

    ListNode current = list1;
    while (current != null) {
        q1.add(current.val);
        current = current.next;
    }
    ...
}