정리된 목록 병합

오늘은 또 다른 연결리스트 작업을 살펴보겠습니다.

2개의 정렬된 연결 목록을 병합하는 함수를 만듭니다. 결과 목록은 2개 목록의 노드를 사용하여 정렬된 목록이어야 합니다.

이를 위해 여기에서 찾을 수 있는 이전 게시물의 일반 연결 목록 구현을 사용합니다

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
    result := LinkedList[int]{}

    p1 := ll1.Head
    p2 := ll2.Head
    rp := &Node[int]{} // dummy node as result head
    result.Head = rp
    for p1 != nil && p2 != nil {
        if p1.Data >= p2.Data {
            rp.Next = p2
            p2 = p2.Next
        } else {
            rp.Next = p1
            p1 = p1.Next
        }
        rp = rp.Next
    }
    if p1 != nil {
        rp.Next = p1
    }
    if p2 != nil {
        rp.Next = p2
    }
    result.Head = result.Head.Next
    return result
}

논리는 따라하기 매우 쉽습니다. 먼저 2개 목록의 헤드와 결과 목록에 대한 포인터를 설정합니다. 결과 목록의 '헤드'를 모르기 때문에 자리 표시자로 더미 노드를 만듭니다(나중에 수정하겠습니다). 또한 결과 목록에 대한 현재 노드 rp를 생성합니다.

다음으로 2개의 목록을 반복합니다. 각 목록에는 현재 노드가 있습니다. 각 단계에서 현재 2개의 노드 중 더 작은 값을 갖는 노드를 살펴보고 해당 노드를 결과 목록에 넣습니다. 그런 다음 해당 목록의 현재 노드(더 작은 노드)를 목록의 다음 노드로 이동합니다. 또한 결과의 현재 노드를 다음 위치로 이동해야 합니다.

우리의 루프 논리는 목록 중 하나의 끝에 도달할 때까지 이 작업을 계속하는 것입니다. 이 시점에서 우리는 목록 중 하나에 대해 비교할 요소가 더 이상 없다는 것을 알고 있습니다. 이미 결과 목록에 있습니다. 따라서 다른 목록의 나머지 노드는 이미 정렬되어 있으므로 결과 끝에 간단히 배치할 수 있습니다.

어떻게 다르게 하시겠습니까? 이것을 최적화할 수 있나요? 댓글로 알려주세요.

감사합니다!

이 게시물의 코드와 이 시리즈의 모든 게시물은 여기에서 확인할 수 있습니다

위 내용은 정리된 목록 병합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!