두 개의 질서 있 는 링크 21 을 통합 합 니 다.

방법 1: 귀속
사고의 방향
우 리 는 다음 과 같이 두 개의 링크 에 있 는 merge 작업 (경계 상황 무시, 예 를 들 어 빈 링크 등) 을 재 귀적 으로 정의 할 수 있다. 즉, 두 개의 링크 의 머리 값 이 비교적 작은 노드 와 나머지 요소 의 merge 작업 결과 가 합 쳐 진 것 이다.알고리즘 은 우리 가 상기 귀속 과정 을 직접 모델 링 하 는 동시에 경계 상황 을 고려 해 야 한다.만약 l1 또는 l2 가 처음부터 빈 링크 였 다 면 어떠한 조작 도 합병 할 필요 가 없 기 때문에 우 리 는 비 빈 링크 로 돌아 가 야 합 니 다.그렇지 않 으 면 우 리 는 l1 과 l2 의 어느 링크 의 머리 노드 의 가치 가 더 작은 지 판단 한 다음 에 다음 에 결과 에 추 가 된 노드 를 재 귀적 으로 결정 해 야 한다.만약 두 개의 체인 시계 가 하나 가 비어 있다 면, 귀속 은 끝난다.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

복잡 도 분석

     ：O(n + m，   n  m           。             l1    l2     （           ），   mergeTwoList               。  ，                ，  O(n+m)。

     ：O(n + m)，   n   m           。     mergeTwoLists           ，                。        mergeTwoLists        n+m  ，         O(n+m)。

방법 2: 교체
사고의 방향
우 리 는 반복 적 인 방법 으로 상술 한 알고리즘 을 실현 할 수 있다.l1 과 l2 가 모두 빈 링크 가 아 닐 때 l1 과 l2 의 어느 링크 의 머리 노드 의 값 이 더 작은 지 판단 하고 작은 값 의 노드 를 결과 에 추가 합 니 다. 한 노드 가 결과 에 추 가 된 후에 해당 하 는 링크 의 노드 를 뒤로 이동 합 니 다.
알고리즘
1. 우선, 우 리 는 보초병 노드 prehead 를 설정 합 니 다. 이것 은 마지막 에 합병 후의 링크 로 쉽게 돌아 갈 수 있 습 니 다.우 리 는 prev 지침 을 유지 합 니 다. 우리 가 해 야 할 일 은 next 지침 을 조정 하 는 것 입 니 다.그 다음 에 우 리 는 l1 또는 l2 가 null 을 가리 킬 때 까지 다음 과 같은 과정 을 반복 합 니 다. 만약 에 l1 현재 노드 의 값 이 l2 보다 작 으 면 우 리 는 l1 현재 노드 를 prev 노드 뒤에 연결 하 는 동시에 l1 지침 을 한 자리 뒤로 이동 합 니 다.그렇지 않 으 면, 우 리 는 l2 에 대해 같은 조작 을 한다.우리 가 어떤 요 소 를 뒤에 연결 하든지 간 에 우 리 는 prev 를 뒤로 옮 겨 야 한다.
2. 순환 이 종 료 될 때 l1 과 l2 는 대부분 비 어 있 습 니 다.입력 한 두 개의 링크 는 모두 질서 가 있 기 때문에 어떤 링크 가 비어 있 든 지 간 에 모든 요 소 는 앞에서 합 쳐 진 링크 의 모든 요소 보다 크다.이것 은 우리 가 비 공 링크 를 합병 링크 의 뒤에 간단하게 연결 하고 합병 링크 로 돌아 가면 된다 는 것 을 의미한다.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        //     l1   l2             ，                    
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

복잡 도 분석

     ：O(n + m) ，   n   m           。         ，l1   l2                ，    while                   。                   ，           O(n+m)。
     ：O(1) 。                。