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

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

Сигнатура метода: Node MergeLists (Node list1, Node list2);

Класс узла ниже:

class Node{
    int data;
    Node next;
}

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

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

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

Рекурсия не требуется, чтобы не выделять новый узел:

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;

}

Вот алгоритм объединения двух отсортированных связанных списков A и 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

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

Смотри, мама, без рекурсии!

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

Итерацию можно выполнить, как показано ниже. Сложность = 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;
}

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

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

}

Простое итеративное решение.

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

Ниже я показываю итеративное решение. Рекурсивное решение было бы более компактным, но, поскольку мы не знаем длины списков, рекурсия может привести к переполнению стека.

Основная идея аналогична шагу слияния в сортировке слиянием; мы храним указатель, соответствующий каждому входному списку; на каждой итерации мы продвигаем указатель, соответствующий меньшему элементу. Однако есть одно важное отличие, когда большинство людей спотыкаются. При сортировке слиянием, поскольку мы используем массив результатов, следующей вставляемой позицией всегда является индекс массива результатов. Для связанного списка нам нужно сохранить указатель на последний элемент отсортированного списка. Указатель может перемещаться от одного входного списка к другому в зависимости от того, какой из них имеет меньший элемент для текущей итерации.

При этом следующий код не требует пояснений.

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

Простой код в javascript для объединения двух связанных списков на месте.

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

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

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

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

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

Пожалуйста, обратитесь к моему сообщению в блоге для 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;
    }      
}

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

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

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

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

2>4список A 1>3 список B

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

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

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;

  }

}

Я подхожу к вопросу следующим образом:

Псевдокод:

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

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

Вначале я создал только один фиктивный узел, чтобы избавить себя от множества условий «если».

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

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

Вот код того, как объединить два отсортированных связанных списка headA и 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;
}