合併兩個未排序的單鏈表

Question

我寫了一個函數合併兩個未排序的單鏈表。我只是將第二個列表中的每個節點添加到原始列表的前面。這似乎只是在工作的時候打印原稿，現合併列表中，新添加的元素是「空」

public SLL mergeUnsorted(SLL otherList) 
{ 
    Iterator itr = otherList.iterator() ; 
    while (itr.hasNext()) 
    { 
     Object elem = itr.next() ; 
     System.out.println(elem) ; // to make sure the elements are retrieved correctly 
     SLLNode ins = new SLLNode(elem, null) ; // make a node out of the element 
     ins.succ = this.first ; // insert the element to the front of the original list 
     this.first = ins ; 
    } 
    return this ; 
} 

從主我調用該函數：

myList = myList.mergeUnsorted(otherList) ; 
printIt(myList) ; 

輸出：

null null null null Hi Hello Salut Ciao 

SLLNode構造器：

public SLLNode(Object ObjElem, SLLNode succ) 
{ 
    this.ObjElem = ObjElem ; 
    this.succ = succ ; 
} 

[編輯]

class SLL 
{ 
    SLLNode first ; 

    public SLL() 
    { 
     first = null ; 
    } 
... 

注意1：鍛鍊狀態，該SLL類數據表示僅包括private SLLNode first ;因此我不能使用任何提及「最後」節點

注2的第一節點：鍛鍊包含一種方法，我很可能需要使用，但我看不出如何。

private SLLNode node(int i) 
{ 
    SLLNode curr = first ; 
    for(int j=0; j<i; j++){ 
     curr = curr.succ ; 
     } 
    return curr ; 
} 

注3：我可以在這裏補充但考慮到我可以使用相同的迭代器打印列表迭代器實現代碼看起來正確的，所以我寧願不弄亂這個帖子太多了。希望沒關係？

[EDIT2]

public static void main(String[] args) 
{ 
    SLL myList = new SLL() ; 
    SLL otherList = new SLL() ; 
    SLLNode a = new SLLNode("xx", null) ; 
    SLLNode b = new SLLNode("yy", null) ; 
    SLLNode c = new SLLNode("ww", null) ; 
    SLLNode d = new SLLNode("aa", null) ; 
    SLLNode e = new SLLNode("rr", null) ; 

    otherList.addFirst(a) ; 
    printIt(otherList) ; 
    otherList.addFirst(b) ; 
    printIt(otherList) ; 
    otherList.addFirst(c) ; 
    printIt(otherList) ; 
    otherList.addFirst(d) ; 
    printIt(otherList) ; 

    SLLNode A = new SLLNode("Hello", null) ; 
    SLLNode B = new SLLNode("Hi", null) ; 
    SLLNode C = new SLLNode("Salut", null) ; 
    SLLNode D = new SLLNode("Ciao", null) ; 
    SLLNode E = new SLLNode("Moin", null) ; 

    myList.addFirst(A) ; 
    printIt(myList) ; 
    myList.addFirst(B) ; 
    printIt(myList) ; 
    myList.addFirst(C) ; 
    printIt(myList) ; 
    myList.addFirst(D) ; 
    printIt(myList) ; 

    myList = myList.mergeUnsorted(otherList) ; 
    printIt(myList) ; 
} 

[EDIT3] @Paulo，如由包括在主要EDIT2產生

xx 
yy xx 
ww yy xx 
aa ww yy xx 
Hello 
Hi Hello 
Salut Hi Hello 
Ciao Salut Hi Hello 
aa 
ww 
yy 
xx 
null null null null Ciao Salut Hi Hello 

注意，行9-12是從打印完成輸出合併函數內的聲明

Answer 1

爲什麼你不改變實現，所以你的最後一個節點在第一個列表中的繼承者指向另一個列表中的第一個節點。

public SLL mergeUnsorted(SLL otherList) 
{ 
    if (otherList != null && otherList.first != null) { 
     SLLNode last = null; 
     Iterator itr = iterator() ; 
     for (itr.hasNext()) 
     { 
      Object elem = itr.next() ; 
      if (elem.succ == null) { 
       last = elem; 
      } 
     } 
     if (last != null) { 
      last.succ = otherList.first; 
     } 
    }  
    return this; 
} 

Answer 2

從你的片段看起來是正確的（但我會用this.first = new SLLNode(elem, this.first)並省略接下來的兩條語句）。您的mergeUnsorted方法打印了什麼？

---

編輯：我不知道什麼是錯的，但顯然你addFirst方法的工作，而直接將無法正常工作。因此，使用這樣的：

public SLL mergeUnsorted(SLL otherList) 
{ 
    Iterator itr = otherList.iterator() ; 
    while (itr.hasNext()) 
    { 
     Object elem = itr.next() ; 
     System.out.println(elem) ; // to make sure the elements are retrieved correctly 
     SLLNode ins = new SLLNode(elem, null) ; // make a node out of the element 
     this.addFirst(ins); 
    } 
    return this ; 
} 

當然，這將增加的元素以相反的順序，但現在同樣的正在發生的事情，太（它只是不工作）。