Merge Two Sorted Lists

LeetCode 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.

풀이

값을 비교해가며 새로운 연결 리스트에 추가한다.
둘 중 하나가 더 짧은 경우 짧은 쪽의 순회가 끝나면 결과 연결 리스트의 tail의 next를 긴 쪽의 다음 순회 차례 노드로 지정한다.

코드

Python

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 or not list2:
            if list1: return list1
            if list2: return list2
            else: return

        result = ListNode(val=min(list1.val, list2.val))
        head = result
        if list1.val <= list2.val: list1 = list1.next
        else: list2 = list2.next

        while list1 and list2:
            new = ListNode(val=min(list1.val, list2.val))
            result.next = new
            result = result.next
            if list1.val <= list2.val: list1 = list1.next
            else: list2 = list2.next

        if list1: result.next = list1
        elif list2: result.next = list2

        return head

Java

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            if (list1 != null) {
                return list1;
            }
            if (list2 != null) {
                return list2;
            }
            return list1;
        }

        ListNode result = new ListNode(Math.min(list1.val, list2.val));
        ListNode head = result;

        if (list1.val <= list2.val) {
            list1 = list1.next;
        } else {
            list2 = list2.next;
        }

        while (list1 != null && list2 != null) {
            ListNode node = new ListNode(Math.min(list1.val, list2.val));
            result.next = node;
            result = result.next;
            if (list1.val <= list2.val) {
                list1 = list1.next;
            } else {
                list2 = list2.next;
            }
        }

        if (list1 != null) {
            result.next = list1;
        } else if (list2 != null) {
            result.next = list2;
        }

        return head;
    }
}