[Algorithm/Java][LeetCode] 21. Merge Two Sorted Lists

[LeetCode] 21. Merge Two Sorted Lists

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

문제접근

두 개의 정렬된 연결리스트를 하나의 정렬된 연결리스트로 합치는 문제이다.
연결리스트에서 가장 중요한 것은 첫번째 노드를 잃어버리면 안되는 것이다.(첫번째를 잃어버리면 다 잃어버린다.)
그래서 MergeList에 아무값이나 넣어서 초기화하고 next부터 첫번째 노드를 연결해 주었다.
temp를 이용해서 next를 연결해 주었고 list1과 list2 둘 중 하나가 null이 될 때까지 두개를 비교해서 더 작은 값을 가진 list를 temp를 이용해서 연결해 주었다.
그리고 마지막에 둘 중 하나가 null이 되면 while문을 빠져나와서 null이 아닌 list를 temp.next에 연결해주고
MergeList.next를 리턴하였다.(MergeList는 내가 초기한 임의의 노드이다.)

Code

/**
 * 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 mergeList = new ListNode(-1); // 비어있는 Head 
        ListNode temp = mergeList;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                // 둘 중 작은 값을 temp 다음 노드로 이어주고 다음 노드로 넘어간다.
                temp.next = list1;
                list1= list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }

        // null이 아닌 list를 next로 넘겨준다. 둘 다 null이면 어떤 값이던 null
        if(list1 == null)
            temp.next = list2;
        else temp.next = list1;

        // mergeList는 그냥 시작용으로 만들어놓은 껍데기 이므로 next가 진짜 시작 노드이다.
        return mergeList.next;
    }
}

어려웠던 점/ 배운 점

연결 리스트를 직접 구현한게 너무 오랜만이라서 처음에는 어떻게 하는지 조금 헷갈렸다. 하지만 주석 처리된 ListNode class 의 메소드를 보고 방향을 잡고 풀었다.