合并自定义双向链表

Question

我有两个定制的双向链表和一个方法 insertAt(int pos,DoublyLinkedList l) 应该在另一个列表的给定索引之前插入列表 l。然而，在使用它之后，什么也没有发生，即使当我在调试器中观察过程时，一切似乎都很顺利。程序编译，它只是不给出任何结果。这是最小的例子：

public class DoublyLinkedList{
private static final class Node {

    protected Object data;

    protected Node next, prev;

    /* Constructor */
    public Node() {

        next = null;

        prev = null;

        data = 0;

    }

    /* Constructor */
    public Node(Object d, Node n, Node p) {

        data = d;

        next = n;

        prev = p;

    }

    /* Function to set link to next node */
    public void setLinkNext(Node n) {

        next = n;

    }

    /* Function to set link to previous node */
    public void setLinkPrev(Node p) {

        prev = p;

    }

    /* Funtion to get link to next node */
    public Node getLinkNext() {

        return next;

    }

    /* Function to get link to previous node */
    public Node getLinkPrev() {

        return prev;

    }

    /* Function to set data to node */
    public void setData(Object d) {

        data = d;

    }

    /* Function to get data from node */
    public Object getData() {

        return data;

    }

}
protected Node start;

protected Node end;

public int size;

/* Constructor */
public DoublyLinkedList() {

    start = null;

    end = null;

    size = 0;

}
public void insertBefore(int pos, DoublyLinkedList l) {


    Node ptr = start;
    if (pos == 1) {
        l.end.setLinkNext(start);
        start.setLinkPrev(l.end);
    } else {
        for (int i = 2; i <= size; i++) {
           if(i==pos){

               ptr.setLinkPrev(l.end);
               l.end.setLinkNext(ptr);

               Node tmp=ptr;
               ptr = ptr.getLinkPrev();
               ptr.setLinkNext(l.start);
               l.start.setLinkNext(tmp);

               size=size()+l.size();
               break;
           }
            ptr=ptr.getLinkNext();
        }

    }

}
public static void main(String[] args) {
    // TODO code application logic here

    DoublyLinkedList list1 = new DoublyLinkedList();
    list1.insertAtEnd("a");
    list1.insertAtEnd("b");
    list1.insertAtEnd("c");
    list1.insertAtEnd("d");
    list1.insertAtEnd("e");

     DoublyLinkedList list2 = new DoublyLinkedList();
    list2.insertAtEnd("1");
    list2.insertAtEnd("2");
    list2.insertAtEnd("3");
    list2.insertAtEnd("4");
    list2.insertAtEnd("5");

    list1.display();
    list2.display();

    list1.insertBefore(3, list2);
    list1.display();
    list1.size();
}
}

任何帮助将不胜感激

Answer 1

问题出在这里：

ptr.setLinkPrev(l.end);
l.end.setLinkNext(ptr);

Node tmp=ptr;
ptr = ptr.getLinkPrev();

//ptr is now the last node of l, not the previous node of original list!!!

//==> you cycle your l list again in the next instruction:
ptr.setLinkNext(l.start);
l.start.setLinkNext(tmp);

size=size()+l.size();
break;

你应该在开始合并之前保存 ptr 的前一个节点...

应该是：

Node tmp = prev.getLinkPrev();
ptr.setLinkPrev(l.end);
l.end.setLinkNext(ptr);

tmp.setLinkNext(l.start);
l.start.setLinkPrev(tmp);
size=size()+l.size();
break;

Answer 2

查看您的这部分代码：

           ptr.setLinkPrev(l.end);
           l.end.setLinkNext(ptr);

           Node tmp=ptr;
           ptr = ptr.getLinkPrev();
           ptr.setLinkNext(l.start);
           l.start.setLinkNext(tmp);

它将新列表的末尾设置为 ptr 的前身，并 link 将其正确返回。
临时变量保存对 ptr 的当前引用。
然后你移动 ptr 来引用它的前身。但是这个前身不是原来列表中ptr的前身。就是上面第(1)步的结果，新列表的尾项！
然后你告诉这个项目，新列表的结尾，到 link 到新列表的开始...新列表现在将变成一个圆圈。但只有单独-linked.
然后你 link 开始的 next 到你保存的 - 旧的 ptr.

因此，您从旧起点开始的 links 仍然走老路 - 他们没有太大变化。但是后面的link坏了，新的link坏了

您认为没有任何变化，因为您的打印方法可能只是遍历列表的前向 link。尝试写另一种向后走的打印方法，它应该会变得有趣...

解决此问题的一种方法是在替换之前保存 ptr 的前任，并将其用于转发-linking 新列表。

Answer 3

我在你们的提示下解决了这个问题，谢谢。

public void insertBefore(int pos, DoublyLinkedList l) {
    checkOutOfBounds(pos);

    Node ptr = start;
    if (pos == 1) {
        l.end.setLinkNext(start);
        start.setLinkPrev(l.end);
        start=l.start;
        size=size()+l.size();
    } else {
        for (int i = 2; i <= size; i++) {
           if(i==pos){
               Node tmp=ptr;
               ptr.setLinkPrev(l.end);
               l.end.setLinkNext(ptr.getLinkNext());


               tmp.setLinkNext(l.start);
               l.start.setLinkPrev(tmp);

               size=size()+l.size();
               break;
           }
            ptr=ptr.getLinkNext();
        }

    }

}

合并自定义双向链表

Merging custom doubly linked list

java

doubly-linked-list