[Java] 21. Merge Two Sorted Lists

문제 풀이에 앞서 해당 문제에서는 LinkedList의 개념을 알아야 하기에 간단히 정리해보겠습니다.

 

LinkedList 란?

LinkedList는 자바에서 제공하는 자료구조 중 하나로, 데이터를 연결된 노드(Node)의 형태로 저장하는 방식을 사용합니다. 각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 구성됩니다.

아래는 LinkedList를 사용한 예제 코드입니다. LinkedList에 문자열을 저장하고, 데이터를 추가, 삭제, 탐색하는 방법을 보여줍니다.

 

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList 생성
        LinkedList<String> linkedList = new LinkedList<>();

        // 데이터 추가
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        // 데이터 출력
        System.out.println("LinkedList: " + linkedList);

        // 데이터 접근
        String firstElement = linkedList.getFirst();
        System.out.println("First Element: " + firstElement);

        // 데이터 삭제
        linkedList.removeLast();

        // 데이터 추가
        linkedList.addLast("Durian");

        // 데이터 출력
        System.out.println("LinkedList after modification: " + linkedList);

        // 데이터 탐색
        boolean containsValue = linkedList.contains("Banana");
        System.out.println("Contains Banana: " + containsValue);

        // LinkedList 크기
        int size = linkedList.size();
        System.out.println("LinkedList size: " + size);
    }
}

위의 예제 코드에서는 LinkedList 객체를 생성하고, add() 메서드를 사용하여 데이터를 추가하고, getFirst() 메서드를 사용하여 첫 번째 데이터에 접근합니다. 또한, removeLast() 메서드를 사용하여 마지막 데이터를 삭제하고, addLast() 메서드를 사용하여 데이터를 마지막에 추가합니다. 마지막으로, contains() 메서드를 사용하여 특정 데이터의 존재 여부를 확인하고, size() 메서드를 사용하여 LinkedList의 크기를 확인합니다.

 

실행 결과는 다음과 같습니다.

LinkedList: [Apple, Banana, Cherry]
First Element: Apple
LinkedList after modification: [Apple, Banana, Durian]
Contains Banana: true
LinkedList size: 3

 

추가적으로 ListNode의 개념도 이해하고 있어야 하는데,
ListNode는 LinkedList에서 현재 값의 위치가 Node의 val이고,
next를 통해 다음 값으로 이동하면서 값들을 활용해주면 됩니다.

 

문제의 주석에 더 자세히 설명해보겠습니다.

---

문제 설명 :

- ListNode를 활용해서 LinkedList를 정렬하는 문제이다.

 

/**
 * 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(-1);
        ListNode current = dummy;
        
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                //list1의 현재 값이 list2의 현재값보다 작거나 같을 때,
                //current에 list1의 값을 넣고, list1은 next로 이동시킨다.
                current.next = list1;
                list1 = list1.next;
            }else{
                current.next = list2;
                list2 = list2.next;
            }
            //current.next 값을 current에 넣어주어 초기화 시켜준다.
            current = current.next;
        }

        //남은 녀석들은 그대로 next에 넣어준다.
        if(list1 != null){
            current.next = list1;
        }

        //남은 녀석들은 그대로 next에 넣어준다.
        if(list2 != null){
            current.next = list2;
        }

        //current로 이동시키며 dummy 데이터를 완성했으니 dummy의 -1이 아닌 0부터의 list를 return 한다.
        return dummy.next;

    }
}

 

해설 :

- dummy라는 ListNode를 하나 만들고, dummy의 노드를 이동하며 움직일 행동대장(?) current를 dummy의 메모리 영역에 연결해준다.

- current를 활용해 list1과 list2의 값들을 dummy에 담아주고, 결과적으로 dummy를 return한다.