Слияние двух отсортированных связанных списков самым эффективным способом

Question

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

//Program to merge two sorted linked lists. 

public class LLMergeSort{ 
static Node head1; 
static Node head2; 
static Node newHead; 

static class Node{ 
    int data; 
    Node next; 

    Node(int d){data=d;next=null;} 
} 

public static void merge(Node head1,Node head2,Node newHead){ 

    Node curr1 = head1; 
    Node curr2 = head2; 

    while(curr1!=null && curr2!=null){ 
     if(curr1.data<curr2.data){ 
      Node new_node = new Node(curr1.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr1 = curr1.next; 
     } 
     else{ 
      Node new_node = new Node(curr2.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr2 = curr2.next; 
     } 
    } 

    if(curr1==null){ 
     while(curr2!=null){ 
      Node new_node = new Node(curr2.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr2 = curr2.next; 
     } 
    } 
    else if(curr2==null){ 
     while(curr1!=null){ 
      Node new_node = new Node(curr1.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr1 = curr1.next; 
     } 
    } 
    print(newHead); 
} 

private static void print(Node newHead){ 

    Node curr = newHead; 
    System.out.println("Linked list after merging both the lists : "); 
    while(curr!=null){ 
     System.out.print("["+curr.data+"]->"); 
     curr = curr.next; 
    } 
    System.out.print("NULL"); 
    System.out.println(); 
} 

public static void main(String[] args) { 

    LLMergeSort ll1 = new LLMergeSort(); 
    ll1.head1 = new Node(11); 
    ll1.head1.next = new Node(10); 
    ll1.head1.next.next = new Node(8); 
    ll1.head1.next.next.next = new Node(6); 

    LLMergeSort ll2 = new LLMergeSort(); 
    ll2.head2 = new Node(18); 
    ll2.head2.next = new Node(15); 
    ll2.head2.next.next = new Node(9); 
    ll2.head2.next.next.next = new Node(7); 
    ll2.head2.next.next.next.next = new Node(2); 

    LLMergeSort ll3 = new LLMergeSort(); 

    ll3.newHead = null; 

    merge(head1,head2,newHead); 

    } 
} 

Я новичок в кодировании, так что если кто-то чувствует, что мои программы не до стандарта, то пожалуйста скажите мне.

Answer 1

Должны ли списки не увеличиваться в стоимости, а не уменьшаться, например 6, 8, 10, 11, против 11, 10, 8, 6?

Поскольку слияние является статическим, нет необходимости иметь класс с head1, head2 и newHead в качестве членов. Все они могут быть локальные ссылки на узел в основном, и слияние() может возвращать ссылку на узел вместо того, чтобы третий параметр:

public static void main(String[] args) { 
    Node head1 = new Node(6); 
    head1.next = new Node(8); 
    // ... 
    Node head2 = new Node(2); 
    head2.next = new Node(7); 
    // ... 
    Node newHead = merge(head1, head2); 

Для слияния(), то проще выделить один «фиктивный» узел, и имеет рабочую ссылку на узел, который начинается в качестве ссылки на узел «фиктивного»:

Node dummy = new Node; // dummy.next will be the merged list 
    Node merged = dummy;  // working reference 

Затем слить и заранее через два списка с использованием merged.next. Когда закончите, верните dummy.next. Вам нужно будет проверить head1 == null или head2 == null в начале. Если head1 == null использовать head2 или наоборот. Не имеет значения, являются ли оба значения равными нулю.