LeetCode - 21.Merge Two Sorted Lists

 

[Must-do Easy Question] 시리즈

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

Merge Two Sorted Lists - LeetCode

---

문제

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

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

---

ListNode 에는 int val, ListNode next, ListNode(int x) 가 주어진다.

두 리스트를 Merge해서 새로운 list를 return 해라. 

 

뭔가 input의 ListNode를 전부 출력시켜보고 싶어졌다.

l1은 l2를 알고 l2는 l3 이렇게 가다가 next가 null이면 끝이니까 이런 방식으로 print를 하게 되면

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.*;
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        
        ListNode nextNode = l1;
        while(true){
            System.out.print(nextNode.val);
            if (nextNode.next != null){
                nextNode = nextNode.next;
            }else{
                break;
            }
        }
        
        System.out.println("");

        
        ListNode nextNode2 = l2;
        while(true){
            System.out.print(nextNode2.val);
            if (nextNode2.next != null){
                nextNode2 = nextNode2.next;
            }else{
                break;
            }
        }
        
        return new ListNode();
        
    }
}

Your input

[1,2,4]
[1,3,4]

stdout

124
134

이렇게 나온다 그럼 값을 비교하면서 두개의 list 를 하나로 합쳐보자!

import java.util.*;
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        
        ListNode nextNode = new ListNode();
        
        while(true){
            System.out.print(nextNode.val);
            if(l1.val >= l2.val){
                nextNode = l2;
                l2 = l2.next;
            }else{
                nextNode = l1;
                l1 = l1.next;
            }
            nextNode = nextNode.next;
            if (nextNode.next == null){
                break;
            }
        }
        
        
        return nextNode;
        
    }
}

합쳐지긴 한것 같은데 nextNode를 return 하면 제일 끝 노드이기 떄문에 정답이 될 수 없다. 

완성된 List의 첫번째 노드를 return 해야 하는데...

 

첫번째 노드를 따로 저장하면 좋을 것 같다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.*;
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode firstNode = new ListNode(0);
        ListNode nextNode = firstNode;

        while (l1 != null && l2 != null) {
            // System.out.print(nextNode.next.val);
            if (l1.val > l2.val) {
                nextNode.next = l2;
                l2 = l2.next;
            } else {
                nextNode.next = l1;
                l1 = l1.next;
            }
            nextNode = nextNode.next;
        }

        if (l1 == null) {
            nextNode.next = l2;
        }
        if (l2 == null) {
            nextNode.next = l1;
        }

        return firstNode.next;

    }
}

 

firstNode를 통해 첫번째 노드를 저장하고 nextNode를 통해 List를 만들었다.

마지막에 l1과 l2 가 각각 null일때 노드를 l2 와 l1 으로 바꾸는 것 까지 추가하였다. 

return 은 firstNode는 항상 0값으로 필요없기 떄문에 그 다음값인 을 반환하였다.

통과~

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.

Memory Usage: 39.6 MB, less than 16.16% of Java online submissions for Merge Two Sorted Lists.

 

 

다른 풀이

Recursion을 쓴 풀이가 많이 보였다.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

사실 while문을 Recursion으로 변환하는건 어렵지 않은 일이지만 나에게는 어려운 일인 것 같다. 

코드를 보면 이해가 가지만 막상 재귀호출로 코드를 짜려고 하면 막막하다....

위 코드는 내 코드의 while 문 안에 if문에서 l1 = l1.next 부분을 재귀함수로 만들어서 마지막에 l1이나 l2가 null일때 return 해주는 방식인 것 같다. l1 과 l2는 재귀호출을 해서 리스트의 첫번째 노드를 유지했기 때문에 나처럼 firstNode를 따로 선언할 필요가 없었다.