为作业创建链表,一个要求是名为 concat 的方法,该方法采用列表参数并将其附加到当前列表的末尾。这个方法没有必要使用递归,但是我们的程序应该大量使用递归。我只是想知道是否有可能为此提出一个递归算法。我们的列表类只有一个头节点,没有其他东西,并且它们不是双向链接的。
我当前的尝试只能递归地追加第一个值。我知道它做错了什么,但我无法想出解决方案。第一种方法是在列表上实际调用的方法,其中列表被传入“连接”。然后,我尝试找到列表的尾部并将它们传递给递归方法。这种“包装”方法是我们的递归方法的强制要求。这是我的尝试,但它显然失败了,因为一旦所有调用从堆栈中弹出,然后重新输入对 concat< 的递归调用,我就无法将节点引用“pt”推进到列表中的下一个节点/em>.如果这可以通过递归实现,您能否告诉我如何将该值推进第一个列表并重新输入递归调用,或者只是解决此问题的更好的通用方法?感谢您抽出时间。
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;
}
这是角色节点:
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;
}
}
我的字符串:
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) {
}
}
最佳答案
要连接两个链表,必须使第一个链表的最后一个节点指向第二个链表的第一个节点。
Node first_list = ... // head node
Node second_list = ... // head node
...
Node last_node = first_list.getLastNode()
last_node.setNext(second_list)
现在集中精力实现getLastNode()
。它可以通过使用递归或迭代非常简单地完成,实际上只需两行。
关于java - 链表串联,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15444475/