合并两个排序的Lnkedlist并在一个新的链接列表中打印

Question

我想编写代码来合并两个排序列表并在另一个列表中显示。

我已经创建了一个函数“Merge”，它将每个List的头部作为它的两个参数并返回新List的头部。我创建了“Display”函数，它需要“列表头部”来显示内部的内容它。 问题是当我试图显示新列表的内容时，它显示Nothing。 这是我的主要功能。

public class Main { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     Linkedlist o=new Linkedlist(); 
     Linkedlist o1=new Linkedlist(); 
     Linkedlist o2=new Linkedlist(); 

     o.insertAtlast(5); 
     o.insertAtlast(10); 
     o.insertAtlast(15); 

     o1.insertAtlast(2); 
     o1.insertAtlast(3); 
     o1.insertAtlast(20); 

     o2.head=o2.mergeList(o.head, o1.head); 
     o2.Display(o2.head); 

    } 

} 

and this is my Linkedlist Class 

public class Linkedlist { 

    static class Node{ 
     int data; 
     Node link; 
     public Node(int data) { 
      this.data=data; 
      this.link=null; 
     } 
    } 

    Node head=null; 

    public void insertAtlast(int data) { 
     Node node=new Node(data); 

     if(head==null) 
      head=node; 
     else 
     { 
      Node ptr=head; 

      while(ptr.link!=null) 
       ptr=ptr.link; 
      ptr.link=node; 
     } 


    } 


    public void Display(Node node) { 
     while(node!=null) { 
      System.out.println(node.data); 
      node=node.link; 
     } 
    } 




    public Node mergeList(Node head1,Node head2) { 
     Node head3=null; 

     if(head1==null) 
      head=head2; 
     else if(head2==null) 
       head=head1; 
     else { 
      while(head1!=null && head2!=null) { 

       if(head==null) { 
        if(head2.data<head1.data) { 
         Node node=new Node(head2.data); 
         head=node; 
         head2=head2.link; 
        } 
        else { 
         Node node=new Node(head1.data); 
         head=node; 
         head1=head1.link; 
        } 
       } 

       else 
       { 
        head3=head; 
        while(head3.link!=null) 
         head=head3.link; 
        if(head2.data<head1.data) { 
         Node node=new Node(head2.data); 
         head3.link=node; 
         head2=head2.link; 
        } 
        else { 
         Node node=new Node(head1.data); 
         head3.link=node; 
         head1=head1.link; 
        } 
       } 

      } 

     } 

     return head; 

    } 

} 

Answer 1

递归合并：

public Node mergeList(Node head1, Node head2) { 
    if (head1 == null) return head2; 
    if (head2 == null) return head1; 

    if (head1.data < head2.data) { 
     head1.link = mergeList(head1.link, head2); 
     return head1; 
    } else { 
     head2.link = mergeList(head2.link, head1); 
     return head2; 
    } 
} 

迭代合并：

public Node mergeList(Node head1, Node head2) { 

    Node head3 = null, cursor = null, cursorH1 = head1, cursorH2 = head2; 

    while (cursorH1 != null && cursorH2 != null) { 
     Node temp; 

     if (cursorH1.data < cursorH2.data) { 
      temp = cursorH1; 
      cursorH1 = cursorH1.link; 
     } else { 
      temp = cursorH2; 
      cursorH2 = cursorH2.link; 
     } 

     if (head3 == null) { 
      cursor = temp; 
      head3 = cursor; 
     } else { 
      cursor.link = temp; 
      cursor = cursor.link; 
     } 
    } 

    if (cursorH1 != null) { 
     if (head3 == null) { 
      head3 = cursorH1; 
     } else { 
      cursor.link = cursorH1; 
     } 
    } 

    if (cursorH2 != null) { 
     if (head3 == null) { 
      head3 = cursorH2; 
     } else { 
      cursor.link = cursorH2; 
     } 
    } 

    return head3; 
}