[Leetcode(릿코드)] 21. Merge Two Sorted Lists (Easy)

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

Merge Two Sorted Lists - LeetCode

---

문제

ListNode 인스턴스 2개를 받아서,

값이 작은거부터 하나씩 추가하여 정렬하여 ListNode를 반환하는 문제이다

예를 들어 l1 = [1,2,4], l2 = [1,3,4]가 주어지면

[1,1,2,3,4,4]로 리턴하면 된다

여기서 ListNode 형태는 아래처럼 주어진다

public static class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

 

해결

l1과 l2를 받아서 해당 인스턴스가 null이 아닐때까지 while을 돌린다
결과를 반환하는 ListNode 객체의 인스턴스인 result 하나 생성한다
현재 위치를 표시하는 ListNode 객체의 인스턴스인 curNode 하나 생성한다
l1이나 l2가 null인 경우, null이 아닌 곳에 값을 가져온다. 그리고 next로 이동
둘 다 null이 아닌 경우 값이 작은 곳에서 가져온다. 그리고 next로 이동
curNode.next에 값을 넣어준다
그리고 현재 노드를 next로 이동시켜준다
최종적으로 result.next를 리턴한다 (초기에 result는 빈 인스턴스로 생성하였고 값은 next부터 넣었다)

시간복잡도는 최대 O(l1 + l2) 이므로 O(N)

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode curNode;
        curNode = result;

        while (l1 != null || l2 != null) {
            if (l1 == null || l2 == null) {
                if (l1 == null) {
                    curNode.next = new ListNode(l2.val);
                    l2 = l2.next;
                } else if (l2 == null) {
                    curNode.next = new ListNode(l1.val);
                    l1 = l1.next;
                }
                curNode = curNode.next;
                continue;
            }

            if (l1.val <= l2.val) {
                curNode.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                curNode.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            curNode = curNode.next;
        }

        return result.next;
    }
}