두 개의 정렬 된 목록 병합 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 자본 하나 Facebook 구글 IBM Microsoft 신탁
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 연결된 목록조회수 40

연결된 목록 선형 속성에서 배열과 매우 유사합니다. 두 개의 정렬 된 배열을 병합하여 전체적으로 정렬 된 배열을 형성 할 수 있습니다. 이 문제에서는 정렬 된 두 개의 연결 목록을 병합해야합니다. 그 자리에 정렬 된 방식으로 두 목록의 요소를 포함하는 새 목록을 반환합니다.

두 개의 정렬 된 목록 병합 Leetcode 솔루션

L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4
1 1 2 3 4 9

접근

이를 수행하는 가장 간단한 방법은 두 포인터 기술. 비어있는 새 목록을 만듭니다. 두 포인터 사이에 더 작은 요소를 추가하고 해당 포인터를 증가시킵니다. 이것은 좋은 접근 방식이지만 공간을 소비하는 추가 목록을 만들어야합니다.

최적의 접근 방식은 작업을 수행하기 위해서만 일정한 공간을 소비해야합니다. 그 자리에서 정렬. 반복적 인 접근 방식을 따를 수 있습니다. 두 목록에 이미 노드가 저장되어 있습니다. 새 목록 포인터와 후속 "다음 포인터”는 메모리의 미리 정의 된 노드를 가리켜 야합니다. 이 과정에서 우리는 아니 새 노드.

알고리즘 (순진한 접근 방식)

  1. 함수 만들기 mergeTwoSortedLists () 두 개의 목록 포인터를 인수로 사용합니다.
  2. 목록 중 하나가 Null 다른 하나 돌려줘
  3. 만들기 임시직 두 목록의 헤드 중 더 작은 노드를 가리키는 변수
  4. 이제 적어도 하나의 노드가 결과에 추가되므로 하나의 헤드가 증가해야합니다.
  5. 이것은 하위 문제를 만듭니다. 따라서 동일한 재귀 함수를 호출하고 temp에 추가하십시오.
  6. List1.value <List2.value 인 경우
    • 온도 = 새로운 ListNode (List1.value) , 임시-> 다음 = mergeTwoSortedLists (List1-> next, List2)
  7. List2.value <= List1.value 인 경우
    • 온도 = 새로운 ListNode (List2.value) , 임시-> 다음 = mergeTwoSortedLists (List1, List2-> next)
  8. 반품 임시직 원하는 목록을 얻으려면

알고리즘 (최적)

  1. 호출 될 새 목록 포인터를 만듭니다. dummy_head.
  2. 유지 "프리 헤드”(포인터 복사) 목록에 액세스 할 수 있도록 머리 주소.
  3. "다음 포인터”of dummy_head는 목록에서 미리 정의 된 노드를 가리 키도록 조작해야합니다. l1l2.
  4. 위의 작업을 다음과 같은 방법으로 수행 할 수 있습니다.
    • 머리에서 시작하는 포인터로 목록을 계속 반복하십시오.
    • 목록 중 하나가 완전히 순회되지 않는 한 :
      • 두 개의 목록 포인터에서 더 작은 값의 노드를 dummy_head, 해당 포인터를 증가시킵니다.
    • 이제 포인터 중 적어도 하나는 없는. 따라서 널이 아닌 더미 머리에 목록.
  5. 반환 머리 더미 목록의.

실시

두 개의 정렬 된 목록을 병합하는 C ++ 프로그램

순진한 접근

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;

    listNode* temp;
    if(l1->value < l2->value)
    {
        temp = new listNode(l1->value);
        temp->next = mergeTwoSortedLists(l1->next , l2);
    }
    else
    {
        temp = new listNode(l2->value);
        temp->next = mergeTwoSortedLists(l1 , l2->next);
    }

    return temp;
}


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}

최적의 방법

#include <bits/stdc++.h>
using namespace std;

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
    while(l1 && l2)
    {
        if(l1->value < l2->value)
        {
            dummy_head->next = l1;
            l1 = l1->next;
        }
        else
        {
            dummy_head->next = l2;
            l2 = l2->next;
        }
        dummy_head = dummy_head->next;
    }

    dummy_head->next = (l1 ? l1 : l2);
    return prehead->next;
}



void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}
1 1 2 3 4 9

두 개의 정렬 된 목록을 병합하는 Java 프로그램

순진한 접근

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        listNode temp;
        if(l1.value < l2.value)
        {
            temp = new listNode(l1.value);
            temp.next = mergeTwoSortedLists(l1.next , l2);
        }
        else
        {
            temp = new listNode(l2.value);
            temp.next = mergeTwoSortedLists(l1 , l2.next);
        }

        return temp;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}

최적의 방법

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        listNode dummy_head = new listNode(-1) , prehead = dummy_head;
        while(l1 != null && l2 != null)
        {
            if(l1.value < l2.value)
            {
                dummy_head.next = l1;
                l1 = l1.next;
            }
            else
            {
                dummy_head.next = l2;
                l2 = l2.next;
            }
            dummy_head = dummy_head.next;
        }

        dummy_head.next = ((l1 != null) ? l1 : l2);
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}
1 1 2 3 4 9

복잡성 분석

시간 복잡성 정렬 된 두 목록을 병합하는 방법

O (N + M), 어디에 NM 두 목록의 길이입니다. 두 가지 접근 방식 모두에서 두 목록을 모두 한 번 탐색하므로 두 알고리즘 모두 선형입니다.

공간 복잡성 정렬 된 두 목록을 병합하는 방법

최적의 접근 방식에서는 포인터 조작. 따라서 변수의 상수 공간은 메모리 사용량을 설명합니다. 따라서 최적의 방법은 다음과 같은 공간 복잡성을 갖습니다. O (1). O (N + M) 공간은 논의 된 순진한 접근법에 사용됩니다.

코멘트를 남겨

Translate »
1