如何合并两个链表

Question

我正在尝试创建一种方法来合并两个链表，以便在我的编程课中进行作业。我在这里真的很困惑，该方法必须具有以下方法签名：

public UnorderedLinkedListInt merge2(UnorderedLinkedListInt list)，因此在我的测试器方法中，它看起来像是list3 = list1.merge2(list2)。当方法仅包含一个列表而不同时包含两个列表时，我对如何进行此设置感到困惑。到目前为止，这是我的代码

    public class UnorderedLinkedListInt extends LinkedListIntClass { 
    //Default constructor 
    public UnorderedLinkedListInt() { 
        super(); 
    }

    public boolean search(int searchItem)  { 
        LinkedListNode current; //variable to traverse the list 
        current = first; 
        while (current != null) 
            if (current.info == searchItem) 
                return true; 
            else 
               current = current.link; 
        return false; 
    }

    public void insertFirst(int newItem) { 
        LinkedListNode newNode;  //variable to create the new node 
        //create and insert newNode before first 
        newNode = new LinkedListNode(newItem, first); 
        first = newNode; 
        if (last == null) 
            last = newNode; 
        count++; 
    }

    public void insertLast(int newItem)  { 
        LinkedListNode newNode; //variable to create the new node 
        //create newNode 
        newNode = new LinkedListNode(newItem, null); 
        if (first == null) { 
            first = newNode; 
            last = newNode; 
        } 
        else { 
            last.link = newNode; 
            last = newNode;

        } 
        count++; 
    }

    public void deleteNode(int deleteItem) { 
        LinkedListNode current; //variable to traverse the list 
        LinkedListNode trailCurrent; //variable just before current 
        boolean found; 
        //Case 1; the list is empty 
        if ( first == null) 
            System.err.println("Cannot delete from an empty list."); 
        else { 
            //Case 2: the node to be deleted is first 
            if (first.info == deleteItem) { 
                first = first.link; 
                if (first == null)  //the list had only one node 
                    last = null; 
                count--; 
            } 
            else {  //search the list for the given info 
                found = false; 
                trailCurrent = first; //trailCurrent points to first node 
                current = first.link; //current points to second node 
                while (current != null && !found) { 
                    if (current.info == deleteItem) 
                        found = true; 
                    else { 
                        trailCurrent = current; 
                        current = current.link; 
                    } 
                } 
                //Case 3; if found, delete the node 
                if (found) { 
                    count--; 
                    trailCurrent.link = current.link; 
                    if (last == current)  //node to be deleted was the last node 
                       last = trailCurrent; 
                } 
                else 
                   System.out.println("Item to be deleted is not in the list."); 
            } 
        } 
    } 
    public void merge(UnorderedLinkedListInt list2){
      UnorderedLinkedListInt list1 = this;

        while (list2.first != null) {//while more data to print 
            list1.insertLast(list2.first.info);
            list2.first = list2.first.link; 
        } 
    }
    public UnorderedLinkedListInt merge2(UnorderedLinkedListInt list2){
      UnorderedLinkedListInt list3 = new UnorderedLinkedListInt(); 
      UnorderedLinkedListInt list1 = this;
      while (list1.first != null) {//while more data to print 
            list3.insertLast(list1.first.info);
            list1.first = list1.first.link; 
        } 
      while (list2.first != null) {//while more data to print 
            list3.insertLast(list2.first.info);
            list2.first = list2.first.link; 
        } 
        return list3;
    }
}

我仍然在确切地了解链表的工作方式上遇到一些麻烦，关于如何设计此方法的任何建议将不胜感激。

Answer 1

在像list1.merge2(list2)这样的方法调用中，该方法将list1接收为隐式“当前对象”，您可以使用this引用对其进行访问。

如果愿意，可以使用其他名称：

public UnorderedLinkedListInt merge2(UnorderedLinkedListInt list2){
    UnorderedLinkedListInt list1 = this;
    // now merge list1 and list2
}

Answer 2

您的第一个列表将是this参考所指向的实际对象。

Answer 3

尝试一下：

 import java.io.*;
 class Node1
 {
     int data;
     Node1 link;

     public Node1()
     {
         data=0;
         link=null;
        }

     Node1 ptr,start,temp,ptr1;

     void create()throws  IOException
     {
         int n;
         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
         System.out.println("Enter first data");
         this.data=Integer.parseInt(br.readLine());
         ptr=this;
         start=ptr;
         char ins ='y';
         do
         {
             System.out.println("Wanna Insert another node???");
             ins=(char)br.read();
             br.read();
             if(ins=='y')
             {
                 temp=new Node1();
                 System.out.println("Enter next data");
                 temp.data=Integer.parseInt(br.readLine());
                 temp.link=null;
                 ptr.link=temp;
                 temp=null;
                 ptr=ptr.link;
                }
            }while(ins=='y');
        }

     void merge()throws IOException
     {
         ptr1=this;
         ptr=this;
         Node1 t=new Node1();
         t.create();
         while(ptr1.link!=null)
         { ptr1=ptr1.link;}
         ptr1.link=t.start;
         ptr1=t=null;
        System.out.println("---------------------------"); 
        System.out.println("Merged LL :\n"); 
         while(ptr!=null)
         {
             System.out.print("-->"+ptr.data);
             ptr=ptr.link;
        }
    }
}