정렬이 된 두 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;
}
}