合并两个未排序的单链表

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 ; 
} 

当然，这将增加的元素以相反的顺序，但现在同样的正在发生的事情，太（它只是不工作）。