Java에서 순서가 지정된 연결 목록을 병합하는 방법

문제

두 개의 오름차순 연결 목록을 새로운 오름차순 연결 목록으로 병합하고 돌아옵니다. 새로운 연결리스트는 주어진 두 연결리스트의 모든 노드를 연결하여 형성됩니다.

예 1:

입력: l1 = [1,2,4], l2 = [1,3,4]
출력: [1,1,2,3,4,4]

예 2:

8e99a69fbe029cd4e2b854e244eab143입력: 128dba7a3a77be0113eb0bea6ea0a5d0l1 = [], l2 = []
8e99a69fbe029cd4e2b854e244eab143출력: 128dba7a3a77be0113eb0bea6ea0a5d0[]

예 3:

입력: l1 = [], l2 = [0]
출력: [0]

Idea

Version 1

• 두 연결 목록(l1, l2)에 빈 연결 목록 nList

• 을 만듭니다. 비어있지 않다면, 두 연결리스트의 첫 번째 요소의 값을 비교하고, 가장 작은 것을 꺼내어 새 연결리스트에 추가합니다. 그런 다음 작은 연결리스트의 헤드 포인터가 다음 비트를 가리키고, nList의 포인터도 다음 비트를 가리킵니다.

• 두 연결 목록이 아직 비어 있지 않으면 계속 반복하세요.

• 두 연결 목록 중 하나가 비어 있으면 비어 있지 않은 연결 목록을 연결하세요. nList의 뒷면

• 마지막으로 nList의 다음 항목을 새로운 연결리스트의 헤드 노드로 반환합니다

버전 2

• 먼저 두 개의 연결리스트가 비어 있는지 확인하고 빈 연결리스트를 직접 반환합니다. 비어 있으면. 비어 있지 않으면 계속해서 아래로 내려가서(

• ) l1과 l2의 헤드 노드 중 어느 것이 더 작은지 확인한 다음 이 노드를 헤드 노드로 저장하면 후속 노드가 이 노드 위에 이어집니다. 한 번에.

• 다음 아이디어는 버전 1과 동일합니다

Answer

버전 1

새 노드를 생성하고 원래 연결 목록을 모두 새 연결 목록으로 전송

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode   = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        all.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        all = all.next;
    }
    all.next = list1 != null ? list1 : list2;
    return head.next;
}

버전 2

다음에서 하나를 선택하세요. 원래 연결 목록을 통합하고 새 메모리를 적용하지 마세요

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null) {
        return list1 == null ? list2 : list1;
    }
    ListNode head = list1.val <= list2.val ? list1 : list2;
    if (list1.val <= list2.val)
        list1 = list1.next;
    else
        list2 = list2.next;
    ListNode tmp = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        tmp.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        tmp = tmp.next;
    }
    tmp.next = list1 != null ? list1 : list2;
    return head;
}

위 내용은 Java에서 순서가 지정된 연결 목록을 병합하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!