Algorithm Study - 002

Problem

---

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

 

 

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

 

Example 1:

 

singly-linked list에 관한 문제이다.

단순 연결 리스트 두 개를 오름차순으로 merge하는 것인데 재귀함수가 떠오른다면 성공.

 

Solution

---

/**
 * 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) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode result;
         
        if(l1.val <= l2.val) {
            result = l1;
            l1.next = mergeTwoLists(l1.next, l2);
        }
        else {
            result = l2;
            l2.next = mergeTwoLists(l1, l2.next);;
             
        }
         
        return result;

    }
}

재귀함수를 이용한 비교방법.

linked-list에 대한 기본적인 지식이 없어 문제를 풀 생각조차 하지 못했다.

 

• Constraints:
  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both l1 and l2 are sorted in non-decreasing order.

제약 조건은 위와 같았지만 리스트에 대한 개념이 없었기에 의미는 없었다.

 

Learn Point

---

1. ListNode에 대한 지식 부족

2. 소스 중 if(l1 == null) return l2; if(l2 == null) return l1; 을 아직도 이해 못하고 있음.