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.

 

 

https://leetcode.com/problems/merge-two-sorted-lists

 

 

풀이

우선 결과를 내보낼 dummy 노드를 하나 만들어 연결하고, 순서를 조정할 index 노드를 생성하여 진행했다.

입력 변수인 list1과 list2를 비교하면서 더 작은 값의 노드를 idx가 따라가며 dummy노드 뒤에 연결하도록 하고, while문이 종료된 이후에는 큰값만 남은 노드리스트만 있을테니 남은 리스트를 연결하도록 했다.

 

 

코드

/**
 * 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) {
        if(list1 == null) {
        	return list2;
        } else if(list2 == null) {
        	return list1;
        }
		
        ListNode dummy = new ListNode(0);
        ListNode idx = dummy;
        
        while(list1 != null && list2 != null) {
        	if(list1.val > list2.val) {
        		idx.next = list2;
        		list2 = list2.next;
        	} else {
        		idx.next = list1;
        		list1 = list1.next;
        	}
        	idx = idx.next;
        }
        
        if(list1 != null) {
        	idx.next = list1;
        } else if(list2 != null) {
        	idx.next = list2;
        }
        
        return dummy.next;
    }
}

 

 

결과

Runtime : 0 ms

Memory Usage : 42.39 MB