Объединение двух отсортированных связанных списков в третий связанный список (ошибка сортировки и объединения)

Question

Следующий код предназначен для выполнения перечисленных задач

1: создать 3 связанных списка 2: заполнить первые два 3: отсортировать первые два 4: объединить первые два связанных списка с третьим, удалив узлы из каждого из первых двух, сохранив данные и вставив их в третий список

код для этого заключается в следующем

import java.util.*;
import java.util.Scanner;

class Node { //stores int values

public int data;
public Node next;

public Node(int d){
    data = d;
    next = null;
}
//-------------------------------------------------------------------
public void displayNode() { 
System.out.print(data);
}
//-------------------------------------------------------------------
}
//-------------------------------------------------------------------
//-------------------------------------------------------------------
class NodeList {

private Node first;

public NodeList(){
    first = null;
}
//-------------------------------------------------------------------
public boolean isEmpty(){
    return first == null;
}
//-------------------------------------------------------------------
public void inputList(int n){

int x = 0;
Node newNode = null;
Node last = null;
Random randomGenerator = new Random();

Scanner in = new Scanner(System.in);

for (int i = 0; i < n; i++){

    //System.out.printf("Enter data for node %d: ", i + 1);
    x = randomGenerator.nextInt(10);
    newNode = new Node(x);

    if (isEmpty()){ 
        first = newNode;
        last = newNode; 
        }
    else { 
        last.next = newNode;
        last = last.next; 
        }
    } 
System.out.println();
}
//-------------------------------------------------------------------
public void selectionSort(){

Node p = null;
Node q = null;
Node r = null;
int t = 0;

if (isEmpty()){
    System.out.println("List is empty");
    }
else if(first.next != null){ 
    p = first;
    while (p.next != null){
        q = first;
        while (q.next != null){
            if (q.data > q.next.data){
                r = q.next;
            }
            q = q.next;
        }
        //System.out.printf("%d\n", r.data);
        t = p.data; 
        p.data = r.data;
        r.data = t;
        p = p.next;
    }
    //System.out.println("List is sorted");
    }
}
//-------------------------------------------------------------------
public int deleteFirst(){ 

    int x = 0;

    if (isEmpty()){
        System.out.println("List is empty");
    }
    else {
        x = first.data;
        first = first.next;
        //System.out.println("First node is deleted");
    }
    return x;
}
//-------------------------------------------------------------------
public void displayList(){

Node curr = null; 

if (isEmpty()){ 
    System.out.println("null");
}
else{
    curr = first;
    while (curr != null){

        curr.displayNode();
        System.out.printf("\n");
        curr = curr.next;
        }
    }
System.out.printf("\n");
}
//-------------------------------------------------------------------
public void insert(int key){ 

    Node prev = null;
    Node curr = first;
    Node newNode = new Node(key);

    while ( (curr != null) &&(curr.data < key) ){

        prev = curr;
        curr = curr.next;
        }

    if (curr == first){
        first = newNode;
        }

    else {
        prev.next = newNode;
        newNode.next = curr;
    }
}
//-------------------------------------------------------------------
}
//-------------------------------------------------------------------
//-------------------------------------------------------------------
class MergeLists {

public static void main(String[] args){
Scanner in = new Scanner(System.in);

NodeList List_A = new NodeList();
NodeList List_B = new NodeList();
NodeList List_C = new NodeList();
String s;
String next;
char choice;
boolean continued = true;

List_A.inputList(5);
List_A.selectionSort();
List_A.displayList();

List_B.inputList(5);
List_B.selectionSort();
List_B.displayList();

while (continued){
System.out.printf("enter choice: \n");
System.out.printf("A: merge two ordered lists\n");
System.out.printf("B: view merged ordered list\n");
System.out.printf("C: exit\n");

s = in.nextLine();
choice = s.charAt(0);

switch(choice){

    case 'a':
        Mergelist(List_A, List_B, List_C);
        break;

    case 'b':
        List_C.displayList();
        break;

    case 'c':
        continued = false;
        break;

    default:
        System.out.print("Invalid entry\n");
    }//end switch
}//end while

}
public static void Mergelist(NodeList a, NodeList b, NodeList c){
    int x = 0;

    if (a.isEmpty() == false){
        while (a.isEmpty() == false){
            x = a.deleteFirst();
            c.insert(x);
        }
    }

    if (b.isEmpty() == false){
        while (b.isEmpty() == false){
            x = b.deleteFirst();
            c.insert(x);
        }
    }
}
}

проблема, однако, с номерами 3 и 4. Код для сортировки списков является ошибочным. Иногда он сортирует его полностью, а иногда почти не сортирует. Кроме того, с 4-м, в некоторых случаях, только 2 узла добавляются в 3-й список, в других случаях все будут добавлены в порядке

Я не уверен, почему третий не сортирует, но я считаю, что проблемы в третьем вызывают проблемы в четвертом

Если вы можете, любая помощь будет оценена