LeetCode: MergeTwoSortedLists

오늘 푼 문제는 처음에는 Array 형태로 input이 주어질 줄 알았는데 아니었다.

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가 주어졌다.
class를 보면 singly-linked list임을 알 수 있다.

문제 풀이

input으로 주어지는 l1, l2는 정렬된 채로 들어온다.
우리는 l1, l2를 merge하되 정렬된 상태로 merge하면 된다.

기본 아이디어는 아래와 같다.

l1과 l2의 현재 노드 값을 비교해 더 작은 노드를 우리가 return할 ListNode에 이어 붙인다.
l1과 l2 중 하나라도 list의 끝까지 도달한다면 while문을 빠져나온다.
l1과 l2 중 next가 남아있는 list를 우리가 return할 ListNode에 이어 붙인다.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode head = new ListNode(0);
        ListNode p = head;
        
        ListNode p1 = l1;
        ListNode p2 = l2;
 
        while(p1 != null && p2 != null) {
            if(p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            }
            else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        
        if(p1 != null) {
            p.next = p1;
        }
        if(p2 != null) {
            p.next = p2;
        }
        
        return head.next;
    }
}