wake-up-neo.com

Zusammenführen zweier sortierter verknüpfter Listen

Dies ist eine der Programmierfragen, die im schriftlichen Test von Microsoft gestellt wurden. Ich gebe die Frage und die Antwort, auf die ich gekommen bin. Die Sache ist meine Antwort, obwohl sie umfassend erscheint (zumindest für mich), ich glaube, dass die Anzahl der Zeilen reduziert werden kann. Es wurde in C gefragt und ich bin eine Java-Person, aber ich habe es geschafft, es zu codieren (meine Antwort enthält möglicherweise zu viele Java-artige Syntaxen).

Ok, hier ist die Frage.

Sie haben zwei Listen, die bereits Sortiert sind. Sie müssen sie zusammenführen und Eine neue Liste ohne neue zusätzliche Knoten zurückgeben. Die zurückgegebene Liste sollte ebenfalls Sortiert sein. 

Die Methodensignatur lautet

Node* MergeLists(Node* list1, Node* list2);

struct Node{
    int data;
    Node *next;
}

Das Folgende ist die Lösung, die ich mir ausgedacht habe:

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

Ich bin sehr zuversichtlich, dass dies verbessert werden kann. Bitte helfen Sie mir herauszufinden, welche Zeilen redundant sind. Bitte zögern Sie nicht, meine Syntaxfehler und Logik zu kritisieren.

Vielen Dank!

23
bragboy

Ihr Code ist mit if- s für die Handhabung von "Sonderfällen" überladen, was ihn sehr aufbläht und das Lesen erschwert. Dies geschieht normalerweise, wenn Sie sich dafür entscheiden, Sonderfälle "nach Code" zu behandeln, anstatt einen Weg zu finden, sie "nach Daten" zu behandeln. Eine Aussage, die David Wheeler zugeschrieben wird, sagt: "Alle Probleme in der Informatik können durch eine andere Ebene der Dereferenzierung gelöst werden". Diese "zusätzliche Ebene der Dereferenzierung" funktioniert in der Regel sehr gut mit Listen und trägt dazu bei, das durch diese _ ifs erzeugte Durcheinander signifikant zu reduzieren.

Um das oben zu veranschaulichen, würde mein Code folgendermaßen aussehen

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

Einige mögen argumentieren, dass die Verwendung einer zusätzlichen Ebene der Indirektion im pnext-Zeiger den Code tatsächlich schwerer lesbar macht. Ich bin damit einverstanden, dass der Ansatz für Neulinge einige Schwierigkeiten bereiten könnte, aber für erfahrene Programmierer sollte dies als Redewendung leicht verdaulich sein.

13
AnT

Der eklatanteste Fehler liegt in Ihrer Schleife, Sie überschreiben mergedList-> next und verlieren den zuvor hinzugefügten Knoten. Das heißt, Ihre zurückgegebene Liste enthält unabhängig von der Eingabe niemals mehr als zwei Knoten.

Es ist schon eine Weile her, seit ich C gemacht habe, aber ich würde es wie folgt machen:

Node* merge(Node* list1, Node* list2) {
    Node* merged = null;
    Node** tail = &merged;

    while (list1 && list2) {
        if (list1->data < list2->data) {
            *tail = list1;
            list1 = list1->next;
        } else {
            *tail = list2;
            list2 = list2->next;
        }
        tail = &((*tail)->next);
    }
    *tail = list1 ? list1 : list2;
    return merged;
}
19
meriton

Mein Take mit einem Testfall

Bisher waren alle Antworten interessant und gut gemacht. Es ist möglich, dass dies eher dem entspricht, was ein Interviewer gerne sehen würde, mit DRY/DIE und TDD. :-)

#include <stdio.h>

typedef struct ns {
    int data;
    struct ns *next;
} Node;

Node l1[] = {
  { 1, &l1[1] },
  { 3, &l1[2] },
  { 5, &l1[3] },
  { 7, &l1[4] },
  { 9, &l1[5] },
  {11, 0 },
};

Node l2[] = {
  { 2, &l2[1] },
  { 4, &l2[2] },
  { 6, 0 },
};

Node* MergeLists(Node* list1, Node* list2) {
  Node *t, **xt;
  for(xt = &t; list1 || list2;) {
    Node **z = list1 == NULL ? &list2 :
               list2 == NULL ? &list1 :
               list1->data < list2->data ? &list1 : &list2;
    *xt = *z;
     xt = &(*z)->next;
    *z  = *xt;
  }
  *xt = NULL;
  return t;
}

int main(void) {
  for(Node *t = MergeLists(l1, l2); t; t = t->next) 
    printf("%d\n", t->data);
  return 0;
}
9
DigitalRoss

Eleganter geht es nicht:

Node* merge2(Node* n1, Node* n2) {
    n1->next = merge(n1->next, n2);
    return n1;
}

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
           (n1->data < n2->data) ?
               merge2(n1, n2) :
               merge2(n2, n1);
}

Vorausgesetzt, Sie verstehen Rekursion, ist dies so klar wie es nur geht.


Ich sollte darauf hinweisen, dass dies nur für die Antwort auf ein Interview von Nutzen ist (wo vermutlich die Klarheit des Denkens mehr Wirkung zeigt, als nur zu zeigen, dass Sie wissen, wie man Programme schreibt). In der Praxis möchten Sie nicht auf diese Weise zusammenführen, da O(n) Stapeltiefe verwendet wird, was wahrscheinlich zu einem Stapelüberlauf führen würde. Es ist auch keine Schwanzrekursion, daher ist es nicht für den Compiler optimierbar.

5

Divide et Impera

(d. h. MergeSort )

4
Luca

Beim Zusammenfügen von Polygen mit AndreyT erhalten wir:

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
             (n1->data < n2->data) ? 
               (n1->next = merge(n1->next, n2), n1) : 
               (n2->next = merge(n2->next, n1), n2)}

Ich kann nicht für diesen einen Kredit beanspruchen, aber er ist am knappsten und zeigt die Symmetrie zwischen den beiden Argumenten. Er führt keine obskuren Hilfsfunktionen ein. Ich bin nicht sicher, ob ein optimierender Compiler hier eine Tail-Rekursion findet, aber ich tue es. Die Einrückung ist eine letzte Berührung.

2
piccolbo

Rekursion verwenden. Der Code lautet wie folgt:

ListNode* mergeTwoSortedLists(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}
2
herohuyongtao

Das ist mein Take. Im Gegensatz zu anderen Lösungen identifiziert und überspringt es aufeinanderfolgende Knoten in einer Liste, die kleiner oder gleich dem Kopfknoten der anderen Liste sind. Der Kopf der anderen Liste wird am Ende einer solchen Sequenz angehängt, und der Vorgang wird nach dem Rollenwechsel wiederholt. Dieser Ansatz minimiert die Anzahl der Zuweisungen an Node.next, während der NULL-Test in jeder Iteration auf eine Einzelprüfung begrenzt wird.

Node * merge(Node *list1, Node *list2)
{
    if (!list1) return list2;
    if (!list2) return list1;

    Node *tmp;

    // compare head nodes and swap lists to guarantee list1 has the smallest node
    if (list1->val > list2->val) {
        tmp = list2;
        list2 = list1;
        list1 = tmp;
    }

    Node *tail = list1;

    do {
        // Advance the tail pointer skipping over all the elements in the result
        // which have smaller or equal value than the first node on list2
        while (tail->next && (tail->next->val <= list2->val)) {
            tail = tail->next;
        }
        // concat list2 at tail of result and make the rest after tail list2 
        tmp = tail->next;
        tail->next = list2;
        tail = list2;
        list2 = tmp;
    } while (list2);

    return list1;
}
0
Ronen

Sie können Rekursion verwenden:

Node* MergeLists(Node *headA, Node* headB)
{

if(headA==NULL){
    return headB;
}else if(headB ==NULL){
    return headA;
}
Node* head = NULL;
if(headA->data <= headB->data){
    head= headA;
    head->next = MergeLists(headA->next,headB);
}else{
    head= headB;
    head->next = MergeLists(headA,headB->next);
}
 return head;
}
0
#include<stdio.h>

typedef struct NODE
{
    int data;
    struct NODE * next;
}NODE;

NODE * func(NODE*,NODE*);
int main()
{
    int i;
    int size;
    int value;
    NODE * head1,*head2,*newNode,*ptr,*final;
    printf("\nPlease enter the number of elements\n");
    scanf("%d",&size);

    for(i=0;i<size;i++)
    {
            printf("List 1\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head1=newNode;
                ptr=newNode;

            }
    }
    for(i=0;i<size;i++)
    {
            printf("\n\nList 2\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head2=newNode;
                ptr=newNode;

            }
    }

    final=func(head1,head2);
    printf("\n\n");
    while (final!=NULL)
    {
        printf("%d -->",final->data);
        final=final->next;
    }
    printf("NULL
    ");
    return 0;
}

NODE* func(NODE* list1, NODE* list2)
{

    NODE* mergedList,*mergeHead=NULL;
    if(list1 == NULL && list2 ==NULL){//if both are NULL, return NULL
        return NULL;
    }
    if(list1 == NULL){//if list1 is NULL, simply return list2
        return list2;
    }
    if(list2 == NULL){//if list2 is NULL, simply return list1
        return list1;
    }
    mergedList = (NODE*)malloc(sizeof(NODE));
    if(list1->data < list2->data){//initialize mergedList pointer to list1 if list1's data is lesser

        mergedList->data=list1->data;
        mergedList->next=NULL;
        list1 = list1->next;

    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList->data=list2->data;
        mergedList->next=NULL;
        list2 = list2->next;

    }
    mergeHead=mergedList;

    while(list1!=NULL && list2!=NULL){
        if(list1->data < list2->data){
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
        }else{
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
        }
    }
    if(list1 == NULL){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
       while(list2!=NULL)
       {
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
       }

    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
    }
    return mergeHead;
}
0
Abhishek Jadhav
public void Merge(LinkList list1, LinkList list2) {
        if (list1.head == null && list2.head == null) {
            System.out.println("Empty list"); //Check if lists are empty
        }
        if (list1.head == null) { //If list1 is empty print list2
            list2.printList();
        }
        if (list2.head == null) { //If list2 is empty print list1
            list1.printList(); 
        }
        LinkList list3 = new LinkList(); //create a new LinkList object for merging
        Node a = list1.head; //Beginning of list1
        Node b = list2.head; //Beginning of list2
        while (a != null && b != null) { //Until list ends
            if (a.value <= b.value) { //Compare values of list1 against list2
                list3.insert(a.value); //Insert values to new list
                a = a.next;
            } else if (a.value >= b.value) {
                list3.insert(b.value);
                b = b.next;
            }  else if (a.value == b.value){ //Insert only unique values and discard repeated values
            list3.insert(a.value);
            a = a.next;
            b = b.next;
        }
        }
        if (a == null) {
            while (b != null) {
                list3.insert(b.value); //If list1 becomes empty, attach rest of the list2 to list3
                b = b.next;
            }
        }
        if (b == null) {
            while (a != null) {
                list3.insert(a.value);
                a = a.next;
            }
        }
        list3.printList(); //print merged list
    }
}

Hallo Leute ! Ich habe mich diesen Monat auf ein Interview vorbereitet, und während ich an diesem Problem arbeitete, ist dies die Lösung, die ich gefunden habe. Ich habe meine Lösung mit vielen von Ihnen hier veröffentlichten Lösungen verglichen und finde mein Programm sehr langwierig. Obwohl ich finde, dass dies einfacher zu verstehen und zu implementieren ist, gibt es in Java eine bessere Lösung für den vorhandenen Code. Ich suche nach einer besseren Zeitkomplexitätslösung. Jede Hilfe/Richtung/Tipp wird geschätzt.

PS: Ich konnte keine Java-Lösung für die oben in C aufgelisteten Programme erstellen, die Zeiger verwendeten.

0
Naveen

Sie können Java 8, Stream API verwenden, um zusammenzuführen, Distinct zu erhalten und zu sortieren. Nachfolgend finden Sie Beispielcode zum Sortieren und Zusammenführen von zwei Listen mit Integer-Elementen

List<Integer> list1= Arrays.asList(2,3,5,8);
List<Integer> list2 = Arrays.asList(3,6,8);

List<Integer> finalList = new ArrayList<>();
finalList.addAll(list1);
finalList.addAll(list2);

List<Integer>  mergeSortedList = 
  finalList.stream()
    .distinct()
    .sorted()
    .collect(Collectors.toList());
System.out.println(mergeSortedList);
0
Rupesh Kumar

Ich habe eine Rekursionsfunktion dafür erstellt. Hier ist meine Lösung:

Node* merge_recursion(Node* l1, Node* l2)
{
        if (!l1)
                return l2;
        if (!l2)
                return l1;

        if (l1->data < l2->data) {
                l1->next = merge_recursion(l1->next, l2);
                return l1;
        } else {
                l2->next = merge_recursion(l1, l2->next);
                return l2;
        }
}

Speichern Sie den Rückkehrzeiger in der neuen Zeigervariable (in main ()/aufrufende Funktion) und durchlaufen Sie die verknüpfte Liste mit dem neuen Zeiger, um die Druckdaten zu drucken. Dies führt zu einer sortierten verbundenen Liste.

0
Brijesh Valera