[leetcode] Merge Two Sorted Lists

Spark Kim·2021년 10월 16일
0

leetcode

목록 보기
6/9

정렬이 된 두 ListNode를 병합하는 문제이다. 물론, 병합할 때에도 값은 정렬된 형태여야 한다.
예를들면 1-2-5-8 라는 List와 1-3-4-7-8 이라는 List가 있다고 가정하면,
1-1-2-3-4-5-7-8-8 이라는 결과가 나와야 한다.
LeetCode 에서는 두 List의 형태를 ListNode 라는 클래스를 주석에 명시하여 알려주었다.

recursion 형태로 문제를 풀이하였다.

/**
 * 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 l1, ListNode l2) {
        ListNode result = null;
        result = merge(l1, l2, result);
        
        return result;
    }
    public ListNode merge(ListNode node1, ListNode node2, ListNode result) {
        if(node1==null && node2==null) {
            return result;
        }
        if(node1!=null && (node2==null || node1.val <= node2.val)) {
            result = new ListNode(node1.val);
            result.next = merge(node1.next, node2, result.next);
        } else if(node2!=null && (node1 == null || node1.val > node2.val)) {
            result = new ListNode(node2.val);
            result.next = merge(node1, node2.next, result.next);
        }
        return result;
    }
}
profile
성장 지향 백엔드 개발자

0개의 댓글