[LeetCode/21/Java]Merge Two Sorted Lists

[LeetCode/21/Java]Merge Two Sorted Lists

풀이

/**
 * 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 && list2 == null) return null;
        if(list2 == null) return list1;
        if(list1 == null) return list2;
        
        ListNode buf = new ListNode();
        ListNode result = buf;

        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                buf.next = list1;
                list1 = list1.next;
            } else {
                buf.next = list2;
                list2 = list2.next;
            }
            buf = buf.next;
        }
        
        if(list1 != null) buf.next = list1;
        else buf.next = list2;
        
        return result.next;
    }
}

후기

두개의 노드를 합쳐서 내림차순 정렬을 하는 처리입니다.

LinkedList개념을 알아야 풀 수 있는 문제입니다.

 

처리방법

1.인자값이 모두 null일 경우에는 그대로 반환합니다.
2.인자값이 둘중 하나가 null일 경우 null이 아닌 인자값을 반환합니다.
3.buf를 생성해서 list의 비교결과를 하나씩 담아놓습니다.
4.buf에 담긴 값은 버리고 다음 값을 반복해서 비교해 나갑니다.
5.한쪽의 list의 비교값이 null이 되었을 경우 남은 list를 buf의 마지막 부분에 모두 추가합니다.

 

time complexity O(N)
space complexity O(N)