Scal dwie posortowane połączone listy

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.

Twitter Facebook LinkedIn Bufor Reddit Tumblr

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.

Spis treści

Przykład

Wkład

szpilka

Wydajność

szpilka

Rodzaje rozwiązań

Rekurencyjne
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

Zdefiniuj przypadek podstawowy: jeśli którakolwiek z połączonych list jest pusta, po prostu zwróć drugą.
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}.
zwraca nagłówek połączonej rekurencyjnie połączonej listy.

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 *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

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

a = rozmiar pierwszej połączonej listy.

b = rozmiar drugiej połączonej listy.

Iteracyjny