[리트코드LeetCode][Easy][JAVA]21. Merge Two Sorted Lists

 

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

Constraints:

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

 

 

---

 

분석

1. 정렬된 리스트1과 리스트2를 주면  두 개의 노드 요소들을 합쳐서(merge) 하나의 리스트로 만들되 오름차순으로 정렬한 리스트여야 함. 
2. 분석 및 코드 작성에 챗지의 도움을 많이 받았습니다... 

 

 

 

---

 

피드백

1. 내가 몰라서 챗지에게 계속 물어보며 헤맸던 부분이 있는데, Java에서 객체를 변수에 할당할 때 변수가 객체의 참조를 저장한다는 점이다. 즉, 
   ListNode a = new ListNode(0);
   ListNode b = a;
   이런 코드가 있을 때 a와 b는 별개의 ListNode가 아니라 같은 ListNode를 가르킨다(복사의 개념이 아니며 같은 메모리 위치를 참조함).
2. 위와 같은 코드의 상태에서,
   b = b.next 
   라고 재할당하게 되면 b는 a.next 의 객체와 같은 것을 가르키게 된다. 내가 제출한 코드에서 결국 아래와 같은 구조로 a.next...로 이어지는 노드들의 값이 변경된다.

while loop를 통해 b = b.next; 로 재할당함으로써 b는 a.next 로 계속 나아가게 됨.

 

 

3. 결국 while에서 변경되는 것은 b 객체인 것처럼 보이지만 실제로는 a.next, a.next.next, a.next.next.next... 가 변경되는 것이다. 처음에 할당한 a.val은 임의의 값이므로 생략하고, a.next를 return 하면 의도했던 값을 return하게 된다.

4. 나는 Linked 관련 알고리즘에 대해 약하다는 것을 다시 한 번 느끼며... 정진하자.

 

 

---

 

답안

// 챗지의 도움을 많이 받았씁니다....

/**
 * 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 list1, ListNode list2) {
        ListNode answer = new ListNode(0);  // 새롭게 생성할 ListNode의 시작점의 기준이 될 변수
        ListNode tmpList = answer;  // 객체 참조를 저장하므로 실제로 answer와 같은 객체가 됨. 속성을 수정할 경우 answer에서 참조되는 객체의 속성도 수정된다.)

        // 리스트가 둘 다 존재하는 동안 반복
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tmpList.next = list1;    // 더 작은 값으로 할당
                list1 = list1.next; // 다음 노드로 이동
            }else{
                tmpList.next = list2;    // 더 작은 값으로 할당
                list2 = list2.next; // 다음 노드로 이동
            }
            tmpList = tmpList.next; // 이 코드를 통해 tmpList가 현재의 tmpList의 next 노드로 변경됨. 
        }

        // 한 리스트가 끝난 후 남은 리스트 처리
        if (list1 != null) {
            tmpList.next = list1;
        } else {
            tmpList.next = list2;
        }
        
        // 실제 시작점은 임의로 생성된 값이므로 실제로 의미있는 값인 next를 반환한다. 
        return answer.next;
    }
}

 

 

 

---

 

다른 사람의 답안

 

/**
 * 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 l, ListNode r) {
        
        ListNode dummy = new ListNode();
        ListNode current = dummy;

        while(l != null && r != null) {
            if(l.val < r.val) {
                current.next = l;
                l = l.next;
            } else {
                current.next = r;
                r = r.next;
            }

            current = current.next;
        }

        rewrite(l, current);
        rewrite(r, current);

        return dummy.next;
    }

    private void rewrite(ListNode source, ListNode target) {
        while(source != null) {
            target.next = source;
            target = target.next;
            source = source.next;
        }
    }

    /* 
        3, 4, 7
        1, 2, 6
        
        l -> 
        r -> null

        joined: 1, 2, 3, 4, 6, 7
    */
}

 

 

 

 

 

---

 

🔗링크