Интервью: объединение двух отсортированных односвязных списков

Это вопрос программирования, заданный во время письменного теста для интервью. «У вас есть два односвязных списка, которые уже отсортированы, вы должны объединить их и вернуть заголовок нового списка без создания каких-либо новых дополнительных узлов. Возвращенный список также должен быть отсортирован»

Подпись метода: Node MergeLists (Node list1, Node list2);

ласс @Node находится ниже:

class Node{
    int data;
    Node next;
}

Я перепробовал много решений, но не создавал лишних узлов. Пожалуйста помоги

Вот сопровождающая запись в блогеhttp: //techieme.in/merging-two-sorted-singly-linked-list

 dharam22 мая 2012 г., 19:59
@ Pier: Это может быть что угодно. Два списка отсортированы по отдельности, и код должен создать третий список, который отсортирован.
 dharam22 мая 2012 г., 19:58
Обратите внимание: я также нашел решение на / Stackoverflow.com вопросы / 2348374 / слияния двух отсортированных списков но это, когда запуск застревает в бесконечном цикле.
 Pier-Alexandre Bouchard22 мая 2012 г., 20:01
Это потому, что если последний элемент list1 меньше первого элемента list2, вы можете просто изменить последний следующий узел на первый головной узел list2.
 Pier-Alexandre Bouchard22 мая 2012 г., 19:57
последний элемент из списка list1 меньше первого элемента из списка list2?
 Hunter McMillen22 мая 2012 г., 20:03
@ Pier-alexandreBouchard Это чрезвычайно оптимистичное представление о том, какой вклад вы получите.

Ответы на вопрос(24)

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

http: //www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.htm

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

Здесь C будет выходным списком.

 Dejell31 дек. 2013 г., 17:31
Вам нужно проверить NULL, так как может быть, что A или B будут пустыми. Еще один способ сделать это - цикл до тех пор, пока A не будет пустым, а B не пусты
 dharam23 мая 2012 г., 08:22
Это возможно, только если вы создаете новый узел. Вопрос ограничивает создание новых узлов.
Решение Вопроса
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;
  }
}
 hyperfkcb31 окт. 2015 г., 07:05
@ StefanHaustein Какой тип возврата для этой функции был void? Как мне его изменить?
 Adrian McCarthy22 мая 2012 г., 22:34
Recursion для произвольно длинных списков - это рецепт переполнения стека. Но я думаю, это переполнение стека. О, ирония! ; -)
 Stefan Haustein06 июл. 2013 г., 20:59
@ PaulChernoch для кода продукта, вы можете использовать итерационную версию ниже ....
 Amit Sharma19 нояб. 2013 г., 21:46
Холодные четкие решения! Я адаптировал этот код для Java, используя дженерики. Код размещен здесь с объяснением Git.io / -DkBuA Контрольные примеры включены в тот же репозиторий.
 Paul Chernoch05 мар. 2013 г., 20:46
Не только для вопросов об интервью! Я в срок, и мне нужно это для производственного кода. Благодарность
// 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;
                }
            }
        }

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.

Код

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

Node * MergeLists (Узел * A, Узел * B) {// обработка угловых случаев

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

}

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;
    }      
}
 slfan09 июн. 2015 г., 23:36
Не могли бы вы дать какое-то объяснение своему коду?
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;
}

который использует связанный список, реализованный java.util. Вы можете просто скопировать вставить код ниже в метод 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);
        }

Рекурсивный путь (вариант ответа Стефана)

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

Рассмотрите ниже связанный список, чтобы визуализировать это

2>4 список А1>3 список Б

Почти такой же ответ (не рекурсивный), как у Стефана, но с небольшим количеством комментариев / значимым именем переменной. Также освещен двойной связанный список в комментариях, если кому-то это интересн

Рассмотрим пример

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;

  }

}
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 Wang28 окт. 2012 г., 05:04
Нет рекурсии и никаких дополнительных объектов не создано. Просто несколько дополнительных ссылок.
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();      
}
 sanjay21 мар. 2016 г., 19:54
Выше кода объединит два отсортированных по отдельности связных списка.

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

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 Haustein23 мая 2012 г., 01:48
Во время собеседования вы обычно хотите начать с самого чистого / самого короткого / самого элегантного решения, которое соответствует критериям, а затем улучшить его, в частности, если есть риск, что в противном случае у вас может не хватить времени.
 cheeken22 мая 2012 г., 22:52
+ 1 - Итеративный подход почти всегда предпочтительнее рекурсии, где это допустимо.
 John B24 сент. 2017 г., 09:39
Я думаюif (list1.next == null) list1.next = list2; может быть простоlist1.next = list2;. Так какwhile (list1.next != null) цикл только что закончился, мы можем быть уверены, чтоlist1.next == null.
 nikhil26 мая 2012 г., 12:44
@ SonDo Прерогатива ОП - выбрать принятый ответ. И нет ничего плохого в том, что ответ был выбран. Если вы считаете, что ответ должен быть принят, вы можете проголосовать за него.
 Vikram Saini26 июл. 2017 г., 21:00
что нужно делать head = list2; list2 = list1; list1 = head; мы не можем просто назначить head = list2;
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;

}
 Shahjahan Khan02 сент. 2015 г., 14:57
икл @ while должен выполняться при условии "или"

как показано ниже. Сложность = 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 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;
}

как я думал, что решение ... я видел решение, которое включает в себя рекурсию, и они довольно удивительны, это результат хорошо функционального и модульного мышления. Я действительно ценю обмен.

Я хотел бы добавить, что рекурсия не будет работать для больших пакетов, вызовы стека будут переполнены; поэтому я решил попробовать итеративный подход ... и вот что я получаю.

Код довольно понятен, я добавил несколько встроенных комментариев, чтобы убедиться в этом.

Если вы не получили его, пожалуйста, сообщите мне, и я улучшу читабельность (возможно, у меня неверная интерпретация моего собственного кода).

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

}

ию здесь, потому что вы можете рекурсировать слишком глубоко и генерировать исключение переполнения стека. Каждое решение использует слишком много строк кода или использует рекурсию. Это чрезвычайно простая реализация Java с уже включенными объявлениями и инициализацией.

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

Prints: 1 2 3 4 5 6 7 8 9 10

 Uncaught Exception28 янв. 2018 г., 16:11
OP хотел найти решение на месте. Он даже не хочет создавать ни одного нового узла для достижения желаемого результата. Ваше решение создает совершенно новый связанный спис
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;
}

ма, рекурсии нет!

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

"без создания каких-либо новых дополнительных узлов", Насколько я понимаю, это не значит, что я не могу иметь указатель (и), который указывает на существующий узел (ы).

Вы не можете достичь этого, не обращаясь к указателям на существующие узлы, даже если вы используете рекурсию для достижения того же самого, система создаст для вас указатели в качестве стеков вызовов. Это как сказать системе добавить указатели, которых вы избегали в своем коде.

Простая функция для достижения того же с дополнительными указателями:

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

}

Ваш ответ на вопрос