[LeetCode] - Merge Two Sorted Lists

두 singly-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.

1차 시도

/**
 * 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; }
 * }
 */
/*
list1, list2가 null이 될 때 까지 순회하면서
임의의 ListNode가 둘 중에 작은 수를 next하게 한다.
그리고 해당 리스트는 다음 노드로 넘어간다
*/
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode mergeList = null;
        
        while(l1 != null || l2 != null) {
            int first = 0;
            int second = 0;
            
            if(l1 != null) first = l1.val;
            if(l2 != null) second = l2.val;
            
            if(first > second) {
                mergeList.next = l1;
                l1 = l1.next;
            } else if(second > first) {
                mergeList.next = l2;
                l2 = l2.next;
            }else {
                mergeList.next = l1;
                mergeList.next = l2;
                l1 = l1.next;
                l2 = l2.next;
            }
            
        }
        return mergeList;
        
    }
}
Run Code Status: Runtime Error
Your input
[1,2,4]
[1,3,4]
java.lang.NullPointerException
  at line 34, Solution.mergeTwoLists

 

내일 계속

 

/**
 * 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; }
 * }
 */

/*
두 리스트를 하나로 정렬하기 위해서는
해당 리스트의 값을 비교하고
작은 node의 다음 행선지를 큰 node로 이어주어야 한다
그 과정에서 작은 노드쪽의 next를 가지고 있을 변수가 필요하다.

1 -> 2 -> 4
1 -> 3 -> 4

1 == 1 => 
l2.next = l1 -> 이 과정에서 l2.next가 원래 가리키던 3에대한 주소를 지우기 때문에 이를 보관할 변수가 필요


*/
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp1 = new ListNode();
        ListNode temp2 = new ListNode();
        
        while(l1 != null || l2 != null) {
            System.out.println(temp1);
            if(l1 != null && l2 != null) {
                if(l1.val > l2.val) {                    
                    temp2.next = l2.next;
                    l2.next = l1;
                } else if(l2.val > l1.val) {
                    temp1.next = l1.next;
                    l2.next = l1;
                }else if(l1.val == l2.val) {
                // 이 부분 수정 해야함
                    mergeList = l2.next;
                    mergeList.next = l1;
                    mergeList.next = l2;
                    l1 = l1.next;
                    l2 = l2.next;
                }
            }else if(l1 != null && l2 == null){
                mergeList.next = l1;
                l1 = l1.next;
            }else if(l1 == null && l2 != null){
                mergeList.next = l2;
                l2 = l2.next;
            }
        }
        return mergeList;
        
    }
}

 

이어주는 노드와 해당 노드의 주소를 기억할 시작 노드

작으면 이어주는 노드가 작은 리스트를 따라가고 그 다음 으로 순회

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode startNode = new ListNode();
        ListNode followNode = startNode;
        
        while(l1 != null && l2 != null) {
            if(l1.val > l2.val) {                    
                followNode.next = l2;
                l2 = l2.next;
            } else {
                followNode.next = l1;
                l1 = l1.next;
            }
            followNode = followNode.next;
            
        }
        if (l1 == null) followNode.next = l2;
        if (l2 == null) followNode.next = l1;
        
        return startNode.next;
    }
}

Runtime: 0 ms
Memory Usage: 38.2 MB