LeetCode(릿코드) - Merge Two Sorted Lists

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

두 개의 정렬된 LinkedList를 하나의 정렬된 List로 병합하는 문제입니다.

예시는 아래와 같습니다.

 

Point

1. 문제에서 주어진 ListNode 클래스를 사용하여 풀이해야 한다.

2. LinkedList의 특징과 Java 주소값 참조 개념에 대해 이해하고 있어야 한다.

 

처음엔 쉬운 문제라고 생각했는데 거의 1시간이 걸렸다.

자료구조를 제대로 이해하고 있다고 착각하고 있었다는 것을 깨닫게 해준 문제..

/**
 * 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 node = new ListNode();
        ListNode head = node;
        
        while(list1 != null || list2 != null) {
            if(list1 == null) {
                node.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            else if(list2 == null) {
                node.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                if(list1.val <= list2.val) {
                    node.next = new ListNode(list1.val);
                    list1 = list1.next;
                } else {
                    node.next = new ListNode(list2.val);
                    list2 = list2.next;
                }
            }
            node = node.next;
        }
        
        return head.next;
    }
}