java 链表串联

Linked List Concatenation

提问by stevenelberger

Working on creating linked lists for an assignment and one requirement is a method named concatwhich takes a list parameter and appends it to the end of the current list. It's not necessary for this method to use recursion, but our programs are supposed to use recursion heavily. I'm just wondering if it's even possible to come up with a recursive algorithm for this. Our list classes only have a head node, nothing else, and they're not doubly linked.

为赋值和一个需求创建链表的工作是一个名为concat的方法，它接受一个列表参数并将其附加到当前列表的末尾。这种方法不需要使用递归，但我们的程序应该大量使用递归。我只是想知道是否有可能为此提出递归算法。我们的列表类只有一个头节点，没有别的，而且它们没有双重链接。

My current attempt can only append the first value recursively. I know what it's doing wrong, but I can't come up with a solution. The first method is what's actually called on a list with a list being passed in to "concatenate". I then attempt to find the tail of the list and pass these in to the recursive method. This "wrapper" method is a mandatory requirement for our recursive methods. Here's my attempt, but it's obviously failing since I'm having trouble advancing the node reference "pt" to the next node in the list once all of the calls pop off the stack and then re-entering recursive calls to concat. If this ispossible with recursion, can you please give me an idea of how to advance this value down the first list and re-enter the recursive calls or maybe just a better general approach towards this problem? Thanks for your time.

我目前的尝试只能递归地附加第一个值。我知道它做错了什么，但我想不出解决办法。第一种方法是在列表上实际调用的方法，其中将列表传递给“连接”。然后我尝试找到列表的尾部并将它们传递给递归方法。这种“包装器”方法是我们递归方法的强制性要求。这是我的尝试，但它显然失败了，因为一旦所有调用都从堆栈中弹出，然后重新输入对concat 的递归调用，我就无法将节点引用“pt”推进到列表中的下一个节点。如果这是可以使用递归，您能否告诉我如何将这个值推进到第一个列表并重新输入递归调用，或者只是解决这个问题的更好的一般方法？谢谢你的时间。

public void concat(MyString list1) {
    CharacterNode tail = null, pt = list1.head;
    // Find the tail of the list
    if (pt == null) {
    } else if (pt.getNext() == null) {
        tail = pt;
    } else {
        while (pt.getNext() != null) {
            pt = pt.getNext();
        }
        tail = pt;
    }
    list1.head = concat(list1.head, tail, list1.head);
}
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
    // Pass in smaller list every time
    // Head traverses down list till the end
    // Add new node with (pt's letter, null link)
    if (lhead == null) {
    // If head is null, we need to add the node
        lhead = new CharacterNode(pt.getCharacter(),null);
    } else if (tail.getNext() == lhead) {
    // If the head is past tail, stop   
    } else {
        // Call concat on a smaller list
        lhead.setNext(concat(lhead.getNext(),tail,pt));
    }
    return lhead;
}

Here's CharacterNode:

这是 CharacterNode：

class CharacterNode {
    private char letter;
    private CharacterNode next;

    public CharacterNode(char ch, CharacterNode link) {
        letter = ch;
        next = link;
    }

    public void setCharacter(char ch) {
        this.letter = ch;
    }

    public char getCharacter() {
        return letter;
    }

    public void setNext(CharacterNode next) {
        this.next = next;
    }

    public CharacterNode getNext() {
        return next;
    }
}

MyString:

我的字符串：

class MyString {
    // member variable pointing to the head of the linked list
    private CharacterNode head;

    // default constructor
    public MyString() {
    }

    // copy constructor
    public MyString(MyString l) {
    }

    // constructor from a String
    public MyString(String s) {
    }

    // for output purposes -- override Object version
    // no spaces between the characters, no line feeds/returns
    public String toString() {
    }

    // create a new node and add it to the head of the list
    public void addHead(char ch) {
    }

    // create a new node and add it to the tail of the list -- "wrapper"
    public void addTail(char ch) {
    }

    // Recursive method for addTail
    private static CharacterNode addTail(CharacterNode L, char letter) {
    }

    // modify the list so it is reversed
    public void reverse() {
    }

    // remove all occurrences of the character from the list -- "wrapper"
    public void removeChar(char ch) {
    }

    // Recursive removeChar method
    private static CharacterNode removeChar(CharacterNode n, char letter) {
    }

    // "wrapper" for recursive length()
    public int length() {
    }

    // Returns the length of the linked list
    private static int length(CharacterNode L) {
    }

    // concatenate a copy of list1 to the end of the list
    public void concat(MyString list1) {
    }

    // recursive method for concat
    private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
    }
}

回答by 9000

To concatenate two linked lists, you have to make the last node of first list to point to first node of the second list.

要连接两个链表，您必须使第一个列表的最后一个节点指向第二个列表的第一个节点。

Node first_list = ...  // head node
Node second_list = ... // head node
...
Node last_node = first_list.getLastNode()
last_node.setNext(second_list)

Now concentrate on implementing getLastNode(). It can be done very simply by using either recursion or iteration, literally in 2 lines.

现在集中精力实施getLastNode(). 它可以通过使用递归或迭代非常简单地完成，字面意思是 2 行。