[LeetCode] 21. Merge Two Sorted Lists

Problem

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

Merge the two lists in a 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.

Solution

Logic

1. 두 연결 리스트의 첫 노드부터 노드가 가진 키 값을 비교하여 우선순위를 정한다.

2. 더미 노드를 생성하여 우선순위가 정해진 노드들을 매달아준다.

3. 위 과정을 반복한다.

   Code

   /**
    * 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 dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null) {
            cur.next = list1.val <= list2.val ? list1 : list2;
            if (list1.val <= list2.val) list1 = list1.next;
            else list2 = list2.next;
            cur = cur.next;
        } cur.next = list1 == null ? list2 : list1; // add last node
        return dummy.next;
    }
   }
   

   Time Complexity

   • 두 연결 리스트 길이의 합을 n이라 가정했을 때, 다음 두 경우의 수가 존재한다.
4. 최선의 경우 : 한 연결 리스트 길이가 0인 경우에는 계산 시간에 상수 시간 소요되므로 O(1)의 시간 복잡도를 가진다.
5. 최악의 경우 : 두 연결 리스트의 모든 노드가 계산에 사용되는 경우에는 두 연결 리스트 길이의 합 만큼 계산 시간이 소요되므로 O(n)의 시간 복잡도를 가진다.