Scal dwie posortowane połączone listy

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Bloomberg Capital One Facebook Google IBM Microsoft wyrocznia
Połączona listaodwiedzajacy 103

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W scalaniu dwa posortowane powiązane listy podaliśmy główny wskaźnik dwóch połączonych list, połącz je w taki sposób, aby uzyskać jedną połączoną listę, która zawiera węzły z wartościami w kolejności posortowanej. zwraca główny wskaźnik scalonej listy połączonej.

Uwagi: scal połączoną listę w miejscu bez użycia dodatkowej przestrzeni.

Przykład

Wkład

Scal dwie posortowane połączone listyszpilka

Wydajność

Scal dwie posortowane połączone listyszpilka

Rodzaje rozwiązań

  1. Rekurencyjne
  2. Iteracyjny

Rekurencyjne

Podejście do łączenia dwóch posortowanych połączonych list

Pomysł polega na rekurencyjnym scaleniu dwóch połączonych list wejściowych w taki sposób, aby zachować posortowaną kolejność na połączonej liście połączonej.

Algorytm

  1. Zdefiniuj przypadek podstawowy: jeśli którakolwiek z połączonych list jest pusta, po prostu zwróć drugą.
  2. Teraz porównaj wartości danych węzłów głównych obu połączonych list (x i y):
    • if x.dane < y.dane => x.next = recurse {x.next, y}.
    • Else => y.next = recurse {x, y.next}.
  3. zwraca nagłówek połączonej rekurencyjnie połączonej listy.

Scal dwie posortowane połączone listyszpilka Scal dwie posortowane połączone listyszpilka Scal dwie posortowane połączone listyszpilka

Realizacja

Program w C ++

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

/* blue print of node */
class Node
{
    public:
    int data;
    Node *next;
    
    Node(int num)
    {
        data = num;
        next = NULL;
    }
};

/* append a node at the end of the Linked List */
Node* insert(Node *head,int data)
{
    if(head == NULL)
        head = new Node(data);
    else
    {
        Node* temp = head;
        while(temp->next != NULL)
        temp = temp->next;
        
        temp->next = new Node(data);
    }
    
    return head;
}

/* print the Linked List */
void print(Node *head)
{
    if(head != NULL)
    {
        cout<<head->data<<" ";
        print(head->next);
    }
}

/* function that merges 2 Linked Lists keeping the Sorted 
Order & returns the head of of the merged Linked List */ 
Node *sortedMerge(Node* x,Node* y)
{
    if(x == NULL)
    return y;
    
    if(y == NULL)
    return x;
    
    if(x->data < y->data)
    {
        x->next = sortedMerge(x->next,y);
        return x;
    }
    else
    {
        y->next = sortedMerge(x,y->next);
        return y;
    }
}

/* function to implement above */
int main()
{
    Node *x = NULL, *y = NULL;
    
    /* construct the first Linked List */
    x = insert(x,3);
    x = insert(x,4);
    x = insert(x,7);
    x = insert(x,9);
    cout<<"First Linked List : ";
    print(x);
    
    cout<<endl;
    
    /* construct the second Linked List */
    y = insert(y,1);
    y = insert(y,2);
    y = insert(y,5);
    y = insert(y,6);
    y = insert(y,8);
    cout<<"Second Linked List : ";
    print(y);
    
    cout<<endl;
    
    /* merge the 2 Linked Lists and print */
    cout<<"Merged Linked List in Sorted Order : ";
    Node *result = sortedMerge(x,y);
    print(result);
    
    return 0;
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Program Java

import java.util.*;
import java.io.*;

class TutorialCup
{
    /* blue print of node */
    static class Node
    {
        int data;
        Node next;
        
        Node(int num)
        {
            data = num;
            next = null;
        }
    };
    
    /* append a node at the end of the Linked List */
    static Node insert(Node head,int data)
    {
        if(head == null)
            head = new Node(data);
        else
        {
            Node temp = head;
            while(temp.next != null)
            temp = temp.next;
            
            temp.next = new Node(data);
        }
        
        return head;
    }
    
    /* print the Linked List */
    static void print(Node head)
    {
        if(head != null)
        {
            System.out.print(head.data + " ");
            print(head.next);
        }
    }
    
    /* function that merges 2 Linked Lists keeping the Sorted 
    Order & returns the head of of the merged Linked List */ 
    static Node sortedMerge(Node x,Node y)
    {
        if(x == null)
        return y;
        
        if(y == null)
        return x;
        
        if(x.data < y.data)
        {
            x.next = sortedMerge(x.next,y);
            return x;
        }
        else
        {
            y.next = sortedMerge(x,y.next);
            return y;
        }
    }
    
    /* function to implement above */
    public static void main (String[] args)
    {
        Node x = null, y = null;
        
        /* construct the first Linked List */
        x = insert(x,3);
        x = insert(x,4);
        x = insert(x,7);
        x = insert(x,9);
        System.out.print("First Linked List : ");
        print(x);
        
        System.out.println();
        
        /* construct the second Linked List */
        y = insert(y,1);
        y = insert(y,2);
        y = insert(y,5);
        y = insert(y,6);
        y = insert(y,8);
        System.out.print("Second Linked List : ");
        print(y);
        
        System.out.println();
        
        /* merge the 2 Linked Lists and print */
        System.out.print("Merged Linked List in Sorted Order : ");
        Node result = sortedMerge(x,y);
        print(result);
    }
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Analiza złożoności

  1. Złożoność czasowa: T (n) = O (a + b).
  2. Złożoność przestrzeni: A (n) = O (1)

a = rozmiar pierwszej połączonej listy.

b = rozmiar drugiej połączonej listy.

Iteracyjny

Podejście do łączenia dwóch posortowanych połączonych list

Chodzi o to, aby przekonwertować kod rekurencyjny na iteracyjny.

Algorytm

  1. tworzy dwa wskaźniki węzłów głowa i ogon.
  2. przydzielać głowa.następny = nowy węzeł (-1), przydzielając fikcyjny węzeł do głowy, aby łatwo było scalić połączoną listę. the głowa wskaźnik służy do zachowania nagłówka scalonej listy połączonej.
  3. ogon służy do przechowywania końca połączonej listy połączonej, rozszerzenie ogon wskaźnik służy do dołączania węzłów z x i y na końcu scalonej listy.
  4. Przechodź zarówno przez listy wejściowe x i y jednocześnie, aż do końca jednego z nich.
  5. Dla każdego węzła x i y rozważ:
    1. if x.data <y.data => ogon.następny = x i przejdź do następnego węzła na liście x.
    2. Więcej ogon.następny = y i przejdź do następnego węzła na liście y.
  6. Jeśli podczas przechodzenia którakolwiek z list x lub y stanie się pusta, po prostu dołącz niepustą listę do scalonej listy.
  7. W końcu wróć głowa.następny.

Scal dwie posortowane połączone listyszpilka Scal dwie posortowane połączone listyszpilka szpilka szpilka szpilka szpilka szpilka

Realizacja

Program w C ++

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

/* blue print of node */
class Node
{
    public:
    int data;
    Node *next;
    
    Node(int num)
    {
        data = num;
        next = NULL;
    }
};

/* append a node at the end of the Linked List */
Node* insert(Node *head,int data)
{
    if(head == NULL)
        head = new Node(data);
    else
    {
        Node* temp = head;
        while(temp->next != NULL)
        temp = temp->next;
        
        temp->next = new Node(data);
    }
    
    return head;
}

/* print the Linked List */
void print(Node *head)
{
    if(head != NULL)
    {
        cout<<head->data<<" ";
        print(head->next);
    }
}

/* function that merges 2 Linked Lists keeping the Sorted 
Order & returns the head of of the merged Linked List */
Node* utility(Node* x,Node* y) 
{ 
    /* head is used to return head of the merged linked list */
    Node *head = new Node(-1);
    /* tail is used to append a node at end 
    of the merged linked list at each step */
    Node *tail = head;
    
    /* process until one of the linked list becomes empty */
    while(x && y)
    {
        if(x->data < y->data)
        {
            tail->next = x;
            x = x->next;
        }
        else
        {
            tail->next = y;
            y = y->next;
        }
        
        tail = tail->next;
    }
    
    /* if any of the linked list gets exhausted 
    append the other one to the merged list */
    if(x == NULL)
    tail->next = y;
    
    if(y == NULL)
    tail->next = x;
    
    return head->next;
} 

/* function to merge two sorted linked 
lists using a utility function */
Node *sortedMerge(Node* x,Node* y)
{
    if (x == NULL) 
        return y; 
    if (y == NULL) 
        return x; 
  
    /* start with the linked list whose head data is the lesser */
    if (x->data < y->data) 
        return utility(x,y); 
    else
        return utility(y,x); 
}

/* function to implement above */
int main()
{
    Node *x = NULL, *y = NULL;
    
    /* construct the first Linked List */
    x = insert(x,3);
    x = insert(x,4);
    x = insert(x,7);
    x = insert(x,9);
    cout<<"First Linked List : ";
    print(x);
    
    cout<<endl;
    
    /* construct the second Linked List */
    y = insert(y,1);
    y = insert(y,2);
    y = insert(y,5);
    y = insert(y,6);
    y = insert(y,8);
    cout<<"Second Linked List : ";
    print(y);
    
    cout<<endl;
    
    /* merge the 2 Linked Lists and print */
    cout<<"Merged Linked List in Sorted Order : ";
    Node *result = sortedMerge(x,y);
    print(result);
    
    return 0;
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Program Java

import java.util.*;
import java.io.*;

class TutorialCup
{
    /* blue print of node */
    static class Node
    {
        int data;
        Node next;
        
        Node(int num)
        {
            data = num;
            next = null;
        }
    };
    
    /* append a node at the end of the Linked List */
    static Node insert(Node head,int data)
    {
        if(head == null)
            head = new Node(data);
        else
        {
            Node temp = head;
            while(temp.next != null)
            temp = temp.next;
            
            temp.next = new Node(data);
        }
        
        return head;
    }
    
    /* print the Linked List */
    static void print(Node head)
    {
        if(head != null)
        {
            System.out.print(head.data + " ");
            print(head.next);
        }
    }
    
    /* function that merges 2 Linked Lists keeping the Sorted 
    Order & returns the head of of the merged Linked List */
    static Node utility(Node x,Node y) 
    { 
        /* head is used to return head of the merged linked list */
        Node head = new Node(-1);
        /* tail is used to append a node at end 
        of the merged linked list at each step */
        Node tail = head;
        
        /* process until one of the linked list becomes empty */
        while(x != null && y != null)
        {
            if(x.data < y.data)
            {
                tail.next = x;
                x = x.next;
            }
            else
            {
                tail.next = y;
                y = y.next;
            }
            
            tail = tail.next;
        }
        
        /* if any of the linked list gets exhausted 
        append the other one to the merged list */
        if(x == null)
        tail.next = y;
        
        if(y == null)
        tail.next = x;
        
        return head.next;
    } 

    /* function to merge two sorted linked 
    lists using a utility function */
    static Node sortedMerge(Node x,Node y)
    {
        if (x == null) 
            return y; 
        if (y == null) 
            return x; 
      
        /* start with the linked list whose head data is the lesser */
        if (x.data < y.data) 
            return utility(x,y); 
        else
            return utility(y,x); 
    }

    
    /* function to implement above */
    public static void main (String[] args)
    {
        Node x = null, y = null;
        
        /* construct the first Linked List */
        x = insert(x,3);
        x = insert(x,4);
        x = insert(x,7);
        x = insert(x,9);
        System.out.print("First Linked List : ");
        print(x);
        
        System.out.println();
        
        /* construct the second Linked List */
        y = insert(y,1);
        y = insert(y,2);
        y = insert(y,5);
        y = insert(y,6);
        y = insert(y,8);
        System.out.print("Second Linked List : ");
        print(y);
        
        System.out.println();
        
        /* merge the 2 Linked Lists and print */
        System.out.print("Merged Linked List in Sorted Order : ");
        Node result = sortedMerge(x,y);
        print(result);
    }
}
First Linked List : 3 4 7 9 
Second Linked List : 1 2 5 6 8 
Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9

Analiza złożoności

  1. Złożoność czasowa: T (n) = O (a + b).
  2. Złożoność przestrzeni: A (n) = O (1), używane są wskaźniki głowy i ogona, które zajmują stałą pamięć.

a = rozmiar pierwszej połączonej listy.

b = rozmiar drugiej połączonej listy.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »