LeetCode_21: 두 개의 질서 있 는 링크 를 합 칩 니 다.

LeetCode 21 번 문제: 두 개의 질서 있 는 링크 를 새로운 질서 있 는 링크 로 합 쳐 되 돌려 줍 니 다.새 링크 는 주어진 두 링크 의 모든 노드 를 연결 하여 구성 된다.
예시:
입력: 1 - > 2 - > 4, 1 - > 3 - > 4 출력: 1 - > 1 - > 2 - > 3 - > 4 - > 4
제 가 생각 하 는 것 은 아주 간단 합 니 다. 두 개의 체인 시 계 를 옮 겨 다 니 고 하나씩 새로운 체인 시계 에 넣 습 니 다. 시간 복잡 도 는 두 개의 링크 의 길이 이 고 공간 복잡 도 는 두 개의 링크 의 길이 입 니 다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode head = new ListNode(0);
        ListNode cur = head;
        
        while(l1 != null && l2 != null){
            
            int value;
            if(l1.val < l2.val){
                value = l1.val;
                l1 = l1.next;
            }else{
                value = l2.val;
                l2 = l2.next;
            }
        
            cur.next = new ListNode(value);
            cur = cur.next;
        }
        while(l1 != null){
            cur.next = new ListNode(l1.val);
            l1 = l1.next;
            cur = cur.next;
        }
         while(l2 != null){
            cur.next = new ListNode(l2.val);
            l2 = l2.next;
            cur = cur.next;
        }
        
        
        return head.next;
        
    }
}

그리고 공식 적 인 해답 을 보 니 다른 것 은 나 보다 훨씬 간단 하 다. 비록 두 개의 링크 를 옮 겨 다 녔 지만 그 는 새로운 노드 가 아니 라 낡은 링크 의 노드 를 현재 링크 에 걸 었 다. 공간 을 절약 할 뿐만 아니 라 여러 줄 의 코드 도 절약 했다. 너무 형편없다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode head = new ListNode(0);
        ListNode pre = head;
        
        while(l1 != null && l2 != null){
            
            if(l1.val < l2.val){
                pre.next = l1; 
                l1 = l1.next;
            }else{
                pre.next = l2;
                l2 = l2.next;
            }
        
            pre = pre.next;
        }
        pre.next = l1 ==null ? l2 : l1;
        
        return head.next;
        
    }
}