Wywiad: łączenie dwóch posortowanych list pojedynczo połączonych

Rekurencja nie powinna być potrzebna, aby uniknąć przydzielania nowego węzła:

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;
}

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;

}

Oto algorytm łączenia dwóch posortowanych list a i 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

Tutaj C będzie listą wyjściową.

Look ma, no recursion!

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;
}

Iterację można wykonać jak poniżej. Złożoność = 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;
}

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;
}

Proste rozwiązanie iteracyjne.

Node * MergeLists(Node * A, Node * B) { // obsługa narożników

//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
}

}

Można to zrobić bez tworzenia dodatkowego węzła, z tylko innym odniesieniem do węzła przechodzącym do parametrów (node temp).

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;
}

Chciałbym podzielić się tym, jak myślałem o rozwiązaniu... widziałem rozwiązanie, które obejmuje rekurencję i są one dość niesamowite, jest wynikiem dobrze Funkcjonalnego i modułowego myślenia. Naprawdę doceniam to, że się tym podzieliłeś.

Chciałbym dodać, że rekurencja nie będzie działać dla dużych liter, wywołania stosu będą przepełnione; więc postanowiłem spróbować podejścia iteracyjnego... i oto co dostaję.

Kod jest dość oczywiste, dodałem kilka komentarzy inline, aby spróbować zapewnić to.

Jeśli go nie rozumiesz, Powiadom mnie, a poprawię czytelność (być może mam wprowadzającą w błąd interpretację własnego kodu).

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;
    }

}

Dlaczego te wszystkie rozwiązania są tak skomplikowane? Nie chcesz używać tutaj rekurencji, ponieważ możesz rekurencyjnie przechodzić zbyt głęboko i rzucać wyjątek przepełnienia stosu. Każde rozwiązanie używa zbyt wielu linii kodu lub używa rekurencji. Jest to niezwykle prosta implementacja Javy z już zawartymi deklaracjami i inicjalizacjami.

    LinkedList<Integer> list1 = new LinkedList<Integer>();
    LinkedList<Integer> list2 = new LinkedList<Integer>();
    LinkedList<Integer> sortedList = new LinkedList<Integer>();
    list1.add(1);
    list1.add(3);
    list1.add(5);
    list1.add(7);
    list1.add(9);

    list2.add(2);
    list2.add(4);
    list2.add(6);
    list2.add(8);
    list2.add(10);

    while (!list1.isEmpty() && !list2.isEmpty())
    {
        Integer first1 = list1.getFirst();
        Integer first2 = list2.getFirst();

        if(first1 < first2)
        {
            sortedList.add(first1);
            list1.removeFirst();
        }
        else if(first2 > first1)
        {
            sortedList.add(first2);
            list2.removeFirst();
        }
        else // if first1 == first2 then default to first1
        {
            sortedList.add(first1);
            list1.removeFirst();
        }
    }

    for (Integer i : list1) // add any remaining values from list1
        sortedList.add(i);

    for (Integer i : list2) // add any remaining values from list2
        sortedList.add(i);

    for (Integer i : sortedList) // print the sorted list
        System.out.println(i);

Wydruków: 1 2 3 4 5 6 7 8 9 10

Przede wszystkim zrozumieć średnią "bez tworzenia nowych dodatkowych węzłów" , Jak rozumiem, nie oznacza to, że nie mogę mieć wskaźnika(wskaźników), który wskazuje na istniejący węzeł(y).

Nie możesz tego osiągnąć bez mówienia o wskaźnikach do istniejących węzłów, nawet jeśli użyjesz rekurencji, aby osiągnąć to samo, system utworzy wskaźniki dla Ciebie jako stosy wywołań. To tak, jakby system dodawał wskaźniki, których uniknąłeś w kodzie.

Prosta funkcja do osiągnięcia to samo z dodatkowym wskaźnikiem :

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;
}

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;
 }

Proszę zapoznać się z moim wpisem na blogu dla http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html

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;
    }      
}

Oto kompletny działający przykład, który używa linked list zaimplementowanej Javy.util. Możesz po prostu skopiować wklej poniższy kod wewnątrz metody main ().

        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);
        }

Sposób rekurencyjny (wariant odpowiedzi Stefana)

 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;
    }

Rozważ poniższą listę, aby zwizualizować to

2>4 Lista A 1>3 lista B

Prawie taka sama odpowiedź (Nie rekurencyjna) jak Stefan, ale z nieco większą ilością komentarzy/znacząca nazwa zmiennej. Również w komentarzach, jeśli ktoś jest zainteresowany

Rozważ przykład

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;

  }

}

Moje podejście do pytania jest następujące:

Pseudokod:

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.

Kod:

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;
}

        /* 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;
    }

}

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;
}

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

    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;
    }

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;
}

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();      
}

Oto Kod jak połączyć dwie posortowane listy połączone headA i 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;
}