Interviewfrage: Führen Sie zwei sortierte, einzeln verknüpfte Listen zusammen, ohne neue Knoten zu erstellen

82

Dies ist eine Programmierfrage, die während eines schriftlichen Tests für ein Interview gestellt wurde. "Sie haben zwei einzeln verknüpfte Listen, die bereits sortiert sind. Sie müssen sie zusammenführen und den Kopf der neuen Liste zurückgeben, ohne neue zusätzliche Knoten zu erstellen. Die zurückgegebene Liste sollte ebenfalls sortiert werden."

Die Methodensignatur lautet: Node MergeLists (Node list1, Node list2);

Die Knotenklasse ist unten:

class Node{
    int data;
    Node next;
}

Ich habe viele Lösungen ausprobiert, aber keine zusätzlichen Knotenschrauben erstellt. Bitte helfen Sie.

Hier ist der dazugehörige Blogeintrag http://techieme.in/merging-two-sorted-singly-linked-list/

Dharam
quelle
Ist das letzte Element aus Liste1 kleiner als das erste Element aus Liste2?
Pier-Alexandre Bouchard
Bitte beachten Sie: Ich habe auch eine Lösung unter stackoverflow.com/questions/2348374/merging-two-sorted-lists gefunden, aber diese bleibt beim Ausführen in einer Endlosschleife hängen .
Dharam
@Pier: Es kann alles sein. Die beiden Listen sind einzeln sortiert und der Code muss eine dritte Liste erstellen, die sortiert ist.
Dharam
Wenn das letzte Element von list1 kleiner als das erste Element von list2 ist, können Sie einfach den letzten nächsten Knoten in den ersten Kopfknoten von list2 ändern.
Pier-Alexandre Bouchard
1
@ Pier-alexandreBouchard Das ist äußerst optimistisch darüber nachzudenken, welche Art von Input Sie erhalten werden.
Hunter McMillen

Antworten:

188
Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}
Stefan Haustein
quelle
112
Die Rekursion auf beliebig langen Listen ist ein Rezept für einen Stapelüberlauf. Aber ich denke, das ist Stack Overflow. Oh die Ironie! ;-)
Adrian McCarthy
Coole, knackige Lösungen! Ich habe diesen Code mithilfe von Generika an Java angepasst. Hier gehosteter Code mit Erläuterung git.io/-DkBuA Testfälle, die im selben Repository enthalten sind.
Amit Sharma
@StefanHaustein Was ist der Rückgabetyp für diese Funktion war ungültig? Wie soll ich es ändern?
Hyperfkcb
@Denise Ich bin nicht sicher, ob ich die Frage verstehe ... Wenn Sie eine ungültige Funktion wünschen, möchten Sie wahrscheinlich den Startknoten von Liste 1 als Startknoten des Ergebnisses behalten und Liste 2 immer in Liste 1 zusammenführen In diesem Fall können Sie das Datenfeld austauschen, wenn list2.data größer ist. Dann ist list2.data immer größer als list1.data und Sie können mit list1.next und list2
Stefan Haustein
Die Laufzeitkomplexität für die hier rekursive und iterative Lösung oder die von hyperfkcb @ vorgeschlagene Variante ist O (n).
Stefan Haustein
115

Eine Rekursion sollte nicht erforderlich sein, um die Zuweisung eines neuen Knotens zu vermeiden:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}
Stefan Haustein
quelle
5
In einem Interview möchten Sie normalerweise mit der saubersten / kürzesten / elegantesten Lösung beginnen, die die Kriterien erfüllt, und sich dann verbessern - insbesondere, wenn das Risiko besteht, dass Ihnen sonst die Zeit ausgeht.
Stefan Haustein
1
@SonDo Es ist das Vorrecht des OP, die akzeptierte Antwort zu wählen. Und an der gewählten Antwort ist nichts auszusetzen. Wenn Sie der Meinung sind, dass dies die akzeptierte Antwort sein sollte, können Sie dafür stimmen.
Nikil
Was ist die Notwendigkeit, head = list2 zu tun? list2 = list1; list1 = head; können wir nicht einfach head = list2 zuweisen;
Vikram Saini
In diesem Fall wird die Zuordnung zu list1.next vom Kopf getrennt. Die Listen werden grundsätzlich zu list1 zusammengeführt. Es ist ähnlich wie der Swap in der Schleife funktioniert.
Stefan Haustein
1
Ich denke if (list1.next == null) list1.next = list2;kann einfach sein list1.next = list2;. Da die while (list1.next != null)Schleife gerade beendet wurde, können wir sicher sein, dass list1.next == null.
John B
12
Node MergeLists(Node node1, Node node2)
{
   if(node1 == null)
      return node2;
   else (node2 == null)
      return node1;

   Node head;
   if(node1.data < node2.data)
   {
      head = node1;
      node1 = node1.next;
   else
   {
      head = node2;
      node2 = node2.next;
   }

   Node current = head;
   while((node1 != null) ||( node2 != null))
   {
      if (node1 == null) {
         current.next = node2;
         return head;
      }
      else if (node2 == null) {
         current.next = node1;
         return head;
      }

      if (node1.data < node2.data)
      {
          current.next = node1;
          current = current.next;

          node1 = node1.next;
      }
      else
      {
          current.next = node2;
          current = current.next;

          node2 = node2.next;
      }
   }
   current.next = NULL // needed to complete the tail of the merged list
   return head;

}
Ben
quelle
1
while-Schleife sollte unter "oder" Bedingung ausgeführt werden
Shahjahan Khan
4

Hier ist der Algorithmus zum Zusammenführen von zwei sortierten verknüpften Listen A und B:

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

Hier wird C die Ausgabeliste sein.

Jainendra
quelle
5
Dies ist nur möglich, wenn Sie einen neuen Knoten erstellen. Die Frage schränkt die Erstellung neuer Knoten ein.
Dharam
1
Sie müssen null aktivieren, da A oder B möglicherweise leer ist. Eine andere Möglichkeit besteht darin, eine Schleife zu
erstellen,
4

Schau ma, keine Rekursion!

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}
Wildplasser
quelle
2

Die Iteration kann wie folgt durchgeführt werden. Komplexität = O (n)

public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) {
    LLNode mergedNode ;
    LLNode tempNode ;      

    if (nodeA == null) {
        return nodeB;
      } 
      if (nodeB == null) {
        return nodeA;
      }     


    if ( nodeA.getData() < nodeB.getData())
    {
        mergedNode = nodeA;
        nodeA = nodeA.getNext();
    }
    else
    {
        mergedNode = nodeB;
        nodeB = nodeB.getNext();
    }

    tempNode = mergedNode; 

    while (nodeA != null && nodeB != null)
    {           

        if ( nodeA.getData() < nodeB.getData())
        {               
            mergedNode.setNext(nodeA);
            nodeA = nodeA.getNext();
        }
        else
        {
            mergedNode.setNext(nodeB);
            nodeB = nodeB.getNext();                
        }       
        mergedNode = mergedNode.getNext();
    }

    if (nodeA != null)
    {
        mergedNode.setNext(nodeA);
    }

    if (nodeB != null)
    {
        mergedNode.setNext(nodeB);
    }       
    return tempNode;
}
Manish
quelle
2
Node mergeList(Node h1, Node h2) {
    if (h1 == null) return h2;
    if (h2 == null) return h1;
    Node head;
    if (h1.data < h2.data) {
        head = h1;
    } else {
        head = h2;
        h2 = h1;
        h1 = head;
    }

    while (h1.next != null && h2 != null) {
        if (h1.next.data < h2.data) {
            h1 = h1.next;
        } else {
            Node afterh2 = h2.next;
            Node afterh1 = h1.next;
            h1.next = h2;
            h2.next = afterh1;

            if (h2.next != null) {
                h2 = afterh2;
            }
        }
    }
    return head;
}
Zhe W.
quelle
1

Dies kann ohne Erstellen des zusätzlichen Knotens erfolgen, wobei nur eine weitere Knotenreferenz an die Parameter übergeben wird (Knotentemperatur).

private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
    if(nodeList1 == null) return nodeList2;
    if(nodeList2 == null) return nodeList1;

    if(nodeList1.data <= nodeList2.data){
        temp = nodeList1;
        temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);
    }
    else{
        temp = nodeList2;
        temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);
    }
    return temp;
}
Deepak
quelle
1

Ich möchte mitteilen, wie ich die Lösung dachte ... Ich sah die Lösung, die Rekursion beinhaltet und sie ist ziemlich erstaunlich, ist das Ergebnis eines gut funktionierenden und modularen Denkens. Ich schätze das Teilen sehr.

Ich möchte hinzufügen, dass die Rekursion bei großen Lits nicht funktioniert, die Stapelaufrufe überlaufen. Also habe ich beschlossen, den iterativen Ansatz auszuprobieren ... und das bekomme ich.

Der Code ist ziemlich selbsterklärend. Ich habe einige Inline-Kommentare hinzugefügt, um dies sicherzustellen.

Wenn Sie es nicht bekommen, benachrichtigen Sie mich bitte und ich werde die Lesbarkeit verbessern (vielleicht habe ich eine irreführende Interpretation meines eigenen Codes).

import java.util.Random;


public class Solution {

    public static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> {

        T data;
        Node next;

        @Override
        public int compareTo(Node<T> otherNode) {
            return data.compareTo(otherNode.data);
        }

        @Override
        public String toString() {
            return ((data != null) ? data.toString() + ((next != null) ? "," + next.toString() : "") : "null");
        }
    }

    public static Node merge(Node firstLeft, Node firstRight) {
        combine(firstLeft, firstRight);
        return Comparision.perform(firstLeft, firstRight).min;

    }

    private static void combine(Node leftNode, Node rightNode) {
        while (leftNode != null && rightNode != null) {
            // get comparision data about "current pair of nodes being analized".
            Comparision comparision = Comparision.perform(leftNode, rightNode);
            // stores references to the next nodes
            Node nextLeft = leftNode.next; 
            Node nextRight = rightNode.next;
            // set the "next node" of the "minor node" between the "current pair of nodes being analized"...
            // ...to be equals the minor node between the "major node" and "the next one of the minor node" of the former comparision.
            comparision.min.next = Comparision.perform(comparision.max, comparision.min.next).min;
            if (comparision.min == leftNode) {
                leftNode = nextLeft;
            } else {
                rightNode = nextRight;
            }
        }
    }

/** Stores references to two nodes viewed as one minimum and one maximum. The static factory method populates properly the instance being build */
    private static class Comparision {

        private final Node min;
        private final Node max;

        private Comparision(Node min, Node max) {
            this.min = min;
            this.max = max;
        }

        private static Comparision perform(Node a, Node b) {
            Node min, max;
            if (a != null && b != null) {
                int comparision = a.compareTo(b);
                if (comparision <= 0) {
                    min = a;
                    max = b;
                } else {
                    min = b;
                    max = a;
                }
            } else {
                max = null;
                min = (a != null) ? a : b;
            }
            return new Comparision(min, max);
        }
    }

// Test example....
    public static void main(String args[]) {
        Node firstLeft = buildList(20);
        Node firstRight = buildList(40);
        Node firstBoth = merge(firstLeft, firstRight);
        System.out.println(firstBoth);
    }

// someone need to write something like this i guess...
    public static Node buildList(int size) {
        Random r = new Random();
        Node<Integer> first = new Node<>();
        first.data = 0;
        first.next = null;
        Node<Integer> current = first;
        Integer last = first.data;
        for (int i = 1; i < size; i++) {
            Node<Integer> node = new Node<>();
            node.data = last + r.nextInt(5);
            last = node.data;
            node.next = null;
            current.next = node;
            current = node;
        }
        return first;
    }

}}

Sieger
quelle
1

Eine einfache iterative Lösung.

Node* MergeLists(Node* A, Node* B)
{
    //handling the corner cases

    //if both lists are empty
    if(!A && !B)
    {
        cout << "List is empty" << endl;
        return 0;
    }
    //either of list is empty
    else if(!A) return B;
    else if(!B) return A;
    else
    {
        Node* head = NULL;//this will be the head of the newList
        Node* previous = NULL;//this will act as the

        /* In this algorithm we will keep the
         previous pointer that will point to the last node of the output list.
         And, as given we have A & B as pointer to the given lists.

         The algorithm will keep on going untill either one of the list become empty.
         Inside of the while loop, it will divide the algorithm in two parts:
            - First, if the head of the output list is not obtained yet
            - Second, if head is already there then we will just compare the values and keep appending to the 'previous' pointer.
         When one of the list become empty we will append the other 'left over' list to the output list.
         */
         while(A && B)
         {
             if(!head)
             {
                 if(A->data <= B->data)
                 {
                     head = A;//setting head of the output list to A
                     previous = A; //initializing previous
                     A = A->next;
                 }
                 else
                 {
                     head = B;//setting head of the output list to B
                     previous = B;//initializing previous
                     B = B->next;
                 }
             }
             else//when head is already set
             {
                 if(A->data <= B->data)
                 {
                     if(previous->next != A)
                         previous->next = A;
                     A = A->next;//Moved A forward but keeping B at the same position
                 }
                 else
                 {
                     if(previous->next != B)
                         previous->next = B;
                     B = B->next; //Moved B forward but keeping A at the same position
                 }
                 previous = previous->next;//Moving the Output list pointer forward
             }
         }
        //at the end either one of the list would finish
        //and we have to append the other list to the output list
        if(!A)
            previous->next = B;

        if(!B)
            previous->next = A;

        return head; //returning the head of the output list
    }
}
Rupinder Ghotra
quelle
1

Ich zeige unten eine iterative Lösung. Eine rekursive Lösung wäre kompakter, aber da wir die Länge der Listen nicht kennen, besteht bei der Rekursion die Gefahr eines Stapelüberlaufs.

Die Grundidee ähnelt dem Zusammenführungsschritt bei der Zusammenführungssortierung. Wir behalten einen Zeiger, der jeder Eingabeliste entspricht. Bei jeder Iteration bewegen wir den Zeiger, der dem kleineren Element entspricht. Es gibt jedoch einen entscheidenden Unterschied, bei dem die meisten Menschen stolpern. Da bei der Zusammenführungssortierung ein Ergebnisarray verwendet wird, ist die nächste einzufügende Position immer der Index des Ergebnisarrays. Für eine verknüpfte Liste müssen wir einen Zeiger auf das letzte Element der sortierten Liste behalten. Der Zeiger kann von einer Eingabeliste zur nächsten springen, je nachdem, welches das kleinere Element für die aktuelle Iteration hat.

Damit sollte der folgende Code selbsterklärend sein.

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode first = l1;
    ListNode second = l2;
    ListNode head = null;
    ListNode last = null;

    while (first != null && second != null) {
        if (first.val < second.val) {
            if (last != null) {
                last.next = first;
            }
            last = first;
            first = first.next;
        } else {
            if (last != null) {
                last.next = second;
            }
            last = second;
            second = second.next;
        }
        if (head == null) {
            head = last;
        }
    }

    if (first == null) {
        last.next = second;
    }
    if (second == null) {
        last.next = first;
    }

    return head;
}
Abhijit Sarkar
quelle
1

Einfacher Code in Javascript zum Zusammenführen von zwei verknüpften Listen.

function mergeLists(l1, l2) {
    let head = new ListNode(0); //dummy
    let curr = head;
    while(l1 && l2) {
        if(l2.val >= l1.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2=l2.next
        }
        curr = curr.next;
    }
    if(!l1){
        curr.next=l2;
    }
    if(!l2){
        curr.next=l1;
    } 
    return head.next;
}
Null Zeiger
quelle
0

Verstehen Sie zunächst den Mittelwert von "ohne neue zusätzliche Knoten zu erstellen" . Soweit ich weiß, bedeutet dies nicht, dass ich keine Zeiger haben kann, die auf einen oder mehrere vorhandene Knoten verweisen.

Sie können dies nicht erreichen, ohne Zeiger auf vorhandene Knoten zu sprechen. Selbst wenn Sie die Rekursion verwenden, um dasselbe zu erreichen, erstellt das System Zeiger für Sie als Aufrufstapel. Es ist so, als würde man dem System sagen, dass es Zeiger hinzufügen soll, die Sie in Ihrem Code vermieden haben.

Einfache Funktion, um dasselbe mit zusätzlichen Zeigern zu erreichen :

typedef struct _LLNode{
    int             value;
    struct _LLNode* next;
}LLNode;


LLNode* CombineSortedLists(LLNode* a,LLNode* b){
    if(NULL == a){
        return b;
    }
    if(NULL == b){
        return a;
    }
    LLNode* root  = NULL;
    if(a->value < b->value){
        root = a;
        a = a->next;
    }
    else{
        root = b;
        b    = b->next;
    }
    LLNode* curr  = root;
    while(1){
        if(a->value < b->value){
            curr->next = a;
            curr = a;
            a=a->next;
            if(NULL == a){
                curr->next = b;
                break;
            }
        }
        else{
            curr->next = b;
            curr = b;
            b=b->next;
            if(NULL == b){
                curr->next = a;
                break;
            }
        }
    }
    return root;
}
Madhu S. Kapoor
quelle
0
Node * merge_sort(Node *a, Node *b){
   Node *result = NULL;
   if(a ==  NULL)
      return b;
   else if(b == NULL)
      return a;

  /* For the first node, we would set the result to either a or b */
    if(a->data <= b->data){
       result = a;
    /* Result's next will point to smaller one in lists 
       starting at a->next  and b */
      result->next = merge_sort(a->next,b);
    }
    else {
      result = b;
     /*Result's next will point to smaller one in lists 
       starting at a and b->next */
       result->next = merge_sort(a,b->next);
    }
    return result;
 }

In meinem Blogbeitrag finden Sie http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html

Jitsceait
quelle
0
Node MergeLists(Node list1, Node list2) {
    //if list is null return other list 
   if(list1 == null)
   {
      return list2;
   }
   else if(list2 == null)
   {
      return list1;
   }
   else
   {
        Node head;
        //Take head pointer to the node which has smaller first data node
        if(list1.data < list2.data)
        {
            head = list1;
            list1 = list1.next;
        }
        else
        {
           head = list2;
           list2 = list2.next;
        }
        Node current = head;
        //loop till both list are not pointing to null
        while(list1 != null || list2 != null)
        {
            //if list1 is null, point rest of list2 by current pointer 
            if(list1 == null){
               current.next = list2;
               return head;
            }
            //if list2 is null, point rest of list1 by current pointer 
            else if(list2 == null){
               current.next = list1;
               return head;
            }
            //compare if list1 node data is smaller than list2 node data, list1 node will be
            //pointed by current pointer
            else if(list1.data < list2.data)
            {
                current.next = list1;
                current = current.next;
                list1 = list1.next;
            }
            else
            {
                current.next = list2;
                current = current.next;
                list2 = list2.next;
            }
        }      
    return head;
    }      
}
PradeepKS
quelle
0

Hier ist ein vollständiges Arbeitsbeispiel, das die implementierte verknüpfte Liste java.util verwendet. Sie können den folgenden Code einfach kopieren und in eine main () -Methode einfügen.

        LinkedList<Integer> dList1 = new LinkedList<Integer>();
        LinkedList<Integer> dList2 = new LinkedList<Integer>();
        LinkedList<Integer> dListMerged = new LinkedList<Integer>();

        dList1.addLast(1);
        dList1.addLast(8);
        dList1.addLast(12);
        dList1.addLast(15);
        dList1.addLast(85);

        dList2.addLast(2);
        dList2.addLast(3);
        dList2.addLast(12);
        dList2.addLast(24);
        dList2.addLast(85);
        dList2.addLast(185);

        int i = 0;
        int y = 0;
        int dList1Size = dList1.size();
        int dList2Size = dList2.size();
        int list1Item = dList1.get(i);
        int list2Item = dList2.get(y);
        while (i < dList1Size || y < dList2Size) {

            if (i < dList1Size) {

                if (list1Item <= list2Item || y >= dList2Size) {
                    dListMerged.addLast(list1Item);
                    i++;
                    if (i < dList1Size) {
                        list1Item = dList1.get(i);
                    }
                }
            }


            if (y < dList2Size) {

                if (list2Item <= list1Item || i >= dList1Size) {
                    dListMerged.addLast(list2Item);
                    y++;
                    if (y < dList2Size) {
                        list2Item = dList2.get(y);
                    }
                }
            }

        }

        for(int x:dListMerged)
        {
            System.out.println(x);
        }
Entwickler747
quelle
0

Rekursiver Weg (Variante der Stefan-Antwort)

 MergeList(Node nodeA, Node nodeB ){
        if(nodeA==null){return nodeB};
        if(nodeB==null){return nodeA};

    if(nodeB.data<nodeA.data){
        Node returnNode = MergeNode(nodeA,nodeB.next);
        nodeB.next = returnNode;
        retturn nodeB;
    }else{
        Node returnNode = MergeNode(nodeA.next,nodeB);
        nodeA.next=returnNode;
        return nodeA;
    }

Betrachten Sie die unten stehende verknüpfte Liste, um dies zu veranschaulichen

2>4Liste A 1>3 Liste B.

Fast dieselbe Antwort (nicht rekursiv) wie Stefan, jedoch mit wenig mehr Kommentaren / aussagekräftigem Variablennamen. Auch doppelt verknüpfte Liste in Kommentaren abgedeckt, wenn jemand interessiert ist

Betrachten Sie das Beispiel

5->10->15>21 // List1

2->3->6->20 //List2

Node MergeLists(List list1, List list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

if(list1.head.data>list2.head.data){
  listB =list2; // loop over this list as its head is smaller
  listA =list1;
} else {
  listA =list2; // loop over this list
  listB =list1;
}


listB.currentNode=listB.head;
listA.currentNode=listA.head;

while(listB.currentNode!=null){

  if(listB.currentNode.data<listA.currentNode.data){
    Node insertFromNode = listB.currentNode.prev; 
    Node startingNode = listA.currentNode;
    Node temp = inserFromNode.next;
    inserFromNode.next = startingNode;
    startingNode.next=temp;

    startingNode.next.prev= startingNode; // for doubly linked list
    startingNode.prev=inserFromNode;  // for doubly linked list


    listB.currentNode= listB.currentNode.next;
    listA.currentNode= listA.currentNode.next;

  } 
  else
  {
    listB.currentNode= listB.currentNode.next;

  }

}
M Sach
quelle
0

Ich nehme die Frage wie folgt an:

Pseudocode:

Compare the two heads A and B. 
If A <= B, then add A and move the head of A to the next node. 
Similarly, if B < A, then add B and move the head of B to the next node B.
If both A and B are NULL then stop and return.
If either of them is NULL, then traverse the non null head till it becomes NULL.

Code:

public Node mergeLists(Node headA, Node headB) {
    Node merge = null;
    // If we have reached the end, then stop.
    while (headA != null || headB != null) {
        // if B is null then keep appending A, else check if value of A is lesser or equal than B
        if (headB == null || (headA != null && headA.data <= headB.data)) {
            // Add the new node, handle addition separately in a new method.
            merge = add(merge, headA.data);
            // Since A is <= B, Move head of A to next node
            headA = headA.next;
        // if A is null then keep appending B, else check if value of B is lesser than A
        } else if (headA == null || (headB != null && headB.data < headA.data)) {
            // Add the new node, handle addition separately in a new method.
            merge = add(merge, headB.data);
            // Since B is < A, Move head of B to next node
            headB = headB.next;
        }
    }
    return merge;
}

public Node add(Node head, int data) {
    Node end = new Node(data);
    if (head == null) {
        return end;
    }

    Node curr = head;
    while (curr.next != null) {
        curr = curr.next;
    }

    curr.next = end;
    return head;
}
RDM
quelle
0
        /* Simple/Elegant Iterative approach in Java*/    
        private static LinkedList mergeLists(LinkedList list1, LinkedList list2) {
                    Node head1 = list1.start;
                    Node head2 = list2.start;
                    if (list1.size == 0)
                    return list2;
                    if (list2.size == 0)
                    return list1;               
                    LinkedList mergeList = new LinkedList();
                    while (head1 != null && head2 != null) {
                        if (head1.getData() < head2.getData()) {
                            int data = head1.getData();
                            mergeList.insert(data);
                            head1 = head1.getNext();
                        } else {
                            int data = head2.getData();
                            mergeList.insert(data);
                            head2 = head2.getNext();
                        }
                    }
                    while (head1 != null) {
                        int data = head1.getData();
                        mergeList.insert(data);
                        head1 = head1.getNext();
                    }
                    while (head2 != null) {
                        int data = head2.getData();
                        mergeList.insert(data);
                        head2 = head2.getNext();
                    }
                    return mergeList;
                }

/* Build-In singly LinkedList class in Java*/
class LinkedList {
    Node start;
    int size = 0;

    void insert(int data) {
        if (start == null)
            start = new Node(data);
        else {
            Node temp = start;
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            temp.setNext(new Node(data));
        }
        size++;
    }

    @Override
    public String toString() {

        String str = "";
        Node temp=start;
        while (temp != null) {
            str += temp.getData() + "-->";
            temp = temp.getNext();
        }
        return str;
    }

}
paras4all
quelle
0
LLNode *mergeSorted(LLNode *h1, LLNode *h2) 
{ 
  LLNode *h3=NULL;
  LLNode *h3l;
  if(h1==NULL && h2==NULL)
    return NULL; 
  if(h1==NULL) 
    return h2; 
  if(h2==NULL) 
    return h1; 
  if(h1->data<h2->data) 
  {
    h3=h1;
    h1=h1->next; 
  }
  else 
  { 
    h3=h2; 
    h2=h2->next; 
  }
  LLNode *oh=h3;
  while(h1!=NULL && h2!=NULL) 
  {
    if(h1->data<h2->data) 
    {
      h3->next=h1;
      h3=h3->next;
      h1=h1->next; 
    } 
    else 
    {
      h3->next=h2; 
      h3=h3->next; 
      h2=h2->next; 
    } 
  } 
  if(h1==NULL)
    h3->next=h2;
  if(h2==NULL)
    h3->next=h1;
  return oh;
}
Rashmika Reddy
quelle
0
// Common code for insert at the end
        private void insertEnd(int data) {
                Node newNode = new Node(data);
                if (head == null) {
                    newNode.next = head;
                    head = tail = newNode;
                    return;
                }
                Node tempNode = tail;
                tempNode.next = newNode;
                tail = newNode;
            }

    private void mergerTwoSortedListInAscOrder(Node tempNode1, Node tempNode2) {

            if (tempNode1 == null && tempNode2 == null)
                return;
            if (tempNode1 == null) {
                head3 = tempNode2;
                return;
            }
            if (tempNode2 == null) {
                head3 = tempNode1;
                return;
            }

            while (tempNode1 != null && tempNode2 != null) {

                if (tempNode1.mData < tempNode2.mData) {
                    insertEndForHead3(tempNode1.mData);
                    tempNode1 = tempNode1.next;
                } else if (tempNode1.mData > tempNode2.mData) {
                    insertEndForHead3(tempNode2.mData);
                    tempNode2 = tempNode2.next;
                } else {
                    insertEndForHead3(tempNode1.mData);
                    insertEndForHead3(tempNode2.mData);
                    tempNode1 = tempNode1.next;
                    tempNode2 = tempNode2.next;
                }

            }
            if (tempNode1 != null) {
                while (tempNode1 != null) {
                    insertEndForHead3(tempNode1.mData);
                    tempNode1 = tempNode1.next;
                }
            }
            if (tempNode2 != null) {
                while (tempNode2 != null) {
                    insertEndForHead3(tempNode2.mData);
                    tempNode2 = tempNode2.next;
                }
            }
        }

:) GlbMP

Manoj Kumar Pandit
quelle
0
public static Node merge(Node h1, Node h2) {

    Node h3 = new Node(0);
    Node current = h3;

    boolean isH1Left = false;
    boolean isH2Left = false;

    while (h1 != null || h2 != null) {
        if (h1.data <= h2.data) {
            current.next = h1;
            h1 = h1.next;
        } else {
            current.next = h2;
            h2 = h2.next;
        }
        current = current.next;

        if (h2 == null && h1 != null) {
            isH1Left = true;
            break;
        }

        if (h1 == null && h2 != null) {
            isH2Left = true;
            break;
        }
    }

    if (isH1Left) {
        while (h1 != null) {
            current.next = h1;
            current = current.next;
            h1 = h1.next;
        }
    } 

    if (isH2Left) {
        while (h2 != null) {
            current.next = h2;
            current = current.next;
            h2 = h2.next;
        }
    }

    h3 = h3.next;

    return h3;
}
Cong Wang
quelle
Keine Rekursion und keine zusätzlichen Objekte erstellt. Nur ein paar zusätzliche Referenzen.
Cong Wang
0

Ich habe am Anfang nur einen Dummy-Knoten erstellt, um mir viele Wenn-Bedingungen zu ersparen.

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode list1Cursor = l1;
        ListNode list2Cursor = l2;

        ListNode currentNode = new ListNode(-1); // Dummy node
        ListNode head = currentNode;

        while (list1Cursor != null && list2Cursor != null)
        {
            if (list1Cursor.val < list2Cursor.val) {
                currentNode.next = list1Cursor;
                list1Cursor = list1Cursor.next;
                currentNode = currentNode.next;
            } else {
                currentNode.next = list2Cursor;
                list2Cursor = list2Cursor.next;
                currentNode = currentNode.next;
            }
        }

        // Complete the rest
        while (list1Cursor != null) {
            currentNode.next = list1Cursor;
            currentNode = currentNode.next;
            list1Cursor = list1Cursor.next;
        }
        while (list2Cursor != null) {
            currentNode.next = list2Cursor;
            currentNode = currentNode.next;
            list2Cursor = list2Cursor.next;
        }

        return head.next;
    }

Basilikum Musa
quelle
-1
private static Node mergeLists(Node L1, Node L2) {

    Node P1 = L1.val < L2.val ? L1 : L2;
    Node P2 = L1.val < L2.val ? L2 : L1;
    Node BigListHead = P1;
    Node tempNode = null;

    while (P1 != null && P2 != null) {
        if (P1.next != null && P1.next.val >P2.val) {
        tempNode = P1.next;
        P1.next = P2;
        P1 = P2;
        P2 = tempNode;
        } else if(P1.next != null) 
        P1 = P1.next;
        else {
        P1.next = P2;
        break;
        }
    }

    return BigListHead;
}
jnthm
quelle
-1
void printLL(){
    NodeLL cur = head;
    if(cur.getNext() == null){
        System.out.println("LL is emplty");
    }else{
        //System.out.println("printing Node");
        while(cur.getNext() != null){
            cur = cur.getNext();
            System.out.print(cur.getData()+ " ");

        }
    }
    System.out.println();
}

void mergeSortedList(NodeLL node1, NodeLL node2){
    NodeLL cur1 = node1.getNext();
    NodeLL cur2 = node2.getNext();

    NodeLL cur = head;
    if(cur1 == null){
        cur = node2;
    }

    if(cur2 == null){
        cur = node1;
    }       
    while(cur1 != null && cur2 != null){

        if(cur1.getData() <= cur2.getData()){
            cur.setNext(cur1);
            cur1 = cur1.getNext();
        }
        else{
            cur.setNext(cur2);
            cur2 = cur2.getNext();
        }
        cur = cur.getNext();
    }       
    while(cur1 != null){
        cur.setNext(cur1);
        cur1 = cur1.getNext();
        cur = cur.getNext();
    }       
    while(cur2 != null){
        cur.setNext(cur2);
        cur2 = cur2.getNext();
        cur = cur.getNext();
    }       
    printLL();      
}
Sanjay
quelle
Der obige Code führt zwei einzeln sortierte verknüpfte Listen zusammen.
Sanjay
-2

Hier ist der Code zum Zusammenführen von zwei sortierten verknüpften Listen headA und headB:

Node* MergeLists1(Node *headA, Node* headB)
{
    Node *p = headA;
    Node *q = headB;
    Node *result = NULL; 
    Node *pp = NULL;
    Node *qq = NULL;
    Node *head = NULL;
    int value1 = 0;
    int value2 = 0;
    if((headA == NULL) && (headB == NULL))
    {
        return NULL;
    }
    if(headA==NULL)
    {
        return headB;
    }
    else if(headB==NULL)
    {
        return headA;
    }
    else
    {
        while((p != NULL) || (q != NULL))
        {
            if((p != NULL) && (q != NULL))
            {
                int value1 = p->data;
                int value2 = q->data;
                if(value1 <= value2)
                {
                    pp = p->next;
                    p->next = NULL;
                    if(result == NULL)
                    {
                        head = result = p;
                    }
                    else
                    {
                        result->next = p;
                        result = p;
                    }
                    p = pp;
                }
                else
                {
                    qq = q->next;
                    q->next = NULL;
                    if(result == NULL)
                    {
                        head = result = q;
                    }
                    else
                    {
                        result->next = q;
                        result = q;
                    }
                    q = qq;
                }
            }
            else
            {
                if(p != NULL)
                {
                    pp = p->next;
                    p->next = NULL;
                    result->next = p;
                    result = p;
                    p = pp;
                }
                if(q != NULL)
                {
                    qq = q->next;
                    q->next = NULL;
                    result->next = q;
                    result = q;
                    q = qq;
                }
            }
        }
    }
    return head;
}
Manisha
quelle