复制节点列表中的所有内容

Question

这个方法，doubleList应该接受一个列表并再次重复节点序列。LinkedIntList应该表现得像整数的ListNode。例如,[1]->[2]->[3]将[1]->[2]->[3]->[1]->[2]->[3]。虽然我设法让它与辅助方法add()一起工作，但我应该不使用辅助方法。我该如何处理这个问题?

ListNode:

public class ListNode {
    public int data;       // data stored in this node
    public ListNode next;  // link to next node in the list
    // post: constructs a node with data 0 and null link
    public ListNode() {
        this(0, null);
    }
    // post: constructs a node with given data and null link
    public ListNode(int data) {
        this(data, null);
    }
    // post: constructs a node with given data and given link
    public ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
    }
}

这是LinkedIntList与工作的帮助器:

public class LinkedIntList {
    private ListNode front;  // first value in the list
    // post: constructs an empty list
    public LinkedIntList() {
        front = null;
    }
    // post: doubles size of array by appending copy of original into end
    public void doubleList() {
        ListNode current = front; // front of this list
        LinkedIntList other = new LinkedIntList(); // stores copy of the original list
        ListNode temp = other.front; // front of other list
        while (current != null) { // puts a copy of current into new list
            other.add(current.data); // adds data to it
            current = current.next;
        }
        temp = other.front; // resets other list to beginning
        while (temp != null) { // readds that copy onto end of this list
            add(temp.data);
            temp = temp.next;       
        }   
    }
    // post: appends the given value to the end of the list (helper)
    public void add(int value) {
        if (front == null) {
            front = new ListNode(value);
        } else {
            ListNode current = front;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new ListNode(value);
        }
    } 
}   

这是我尝试使用的帮助。这有什么不对吗?它似乎没有把另一个列表附加到这个列表的末尾。

   public void doubleList() {
        ListNode current = front; // front of this list
        LinkedIntList other = new LinkedIntList(); // stores copy of the original list
        ListNode temp = other.front; // front of other list
        while (current != null) { // puts copy of current onto temp
            temp = new ListNode(current.data);
            temp = temp.next;
            current = current.next;
        }
        temp = other.front; // reset temp to front
        while (temp != null) { // goes through temp to add to end of current
            current = new ListNode(temp.data);
            temp = temp.next;
        }
    } 

Answer 1

第二个doubleList()方法的问题:

这些行:

    LinkedIntList other = new LinkedIntList(); // stores copy of the original list
    ListNode temp = other.front; // front of other list

等价于:

    LinkedIntList other = new LinkedIntList(); // stores copy of the original list
    ListNode temp = null;

由于front在新列表中为空。

另外，

        temp = new ListNode(current.data);
        temp = temp.next;

等价于:

        temp = new ListNode(current.data);
        temp = null;

这意味着您正在创建彼此不连接的节点。

为了链接节点，必须更新temp.next.

你可以这样创建复制节点:

    current = front; // front of this list
    ListNode prev = null;
    ListNode frontOther = null;
    while (current != null) {
        temp = new ListNode(current.data);
        if (prev != null) {
            prev.next = temp; // link the previous node to the new node
        } else {
            frontOther = temp; // keep a reference to the first node of the new nodes
        }
        prev = temp;
        current = current.next;
    }

然后你可以将它们连接到原始列表的末尾:

    current = front; // front of this list
    while (current.next != null) {
        current = current.next;
    }
    current.next = frontOther; // link the end of the original list to the duplicated nodes