合并两个未排序的单链表

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

主函数中的“null”，我调用该函数：

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 中包含的 main 生成的完整输出

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 行来自合并函数内的 print 语句

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

当然，这会以相反的顺序添加元素，但现在也会发生同样的情况（它只是不起作用）。