0

我需要递归地编写 find 方法，当我试图找到 x 并找到它时，我需要将 x 移动到链表的头部

例如，如果列表是 head --> 15 --> 20 --> 5 --> 10

然后我运行 find(5)，然后列表将是 head --> 5 --> 15 --> 20 --> 10

private boolean find (int x)
{
    Node pointer = head;
    int i = 0;
    while(pointer != null)
    {
        if( pointer.data != x)
        {
            pointer = pointer.next;
            find(x);      
        }
        else
        {
            return true;
        }
    } 
}
4

3 回答 3

1

我认为您应该编写一个递归辅助方法，例如：

private boolean find(int x, Node node) {
    if (node == null)
        return false;
    return node.data == x || find(x, node.next);
}

那么标准find就是

private boolean find(int x) {
    return find(x, head);  // start search from head
}

考虑到这种方法，添加/删除组件应该不难实现：您可以在第find一种方法中删除适当的节点（如果找到），并在第二种方法中将节点添加到列表的前面find作为包含x(假设find(x, head)返回真）。

于 2012-11-27T01:49:03.950 回答
0

Private boolean find(int x) { Node retval = recursiveFind(x, head, parent) If retVal != null RetVal.next = head Return true }

Private Node recursiveFind(Int x, node head, node parent) { If head == null && parent == null Return null;

如果 head.value == x Parent.next = head.next：返回 head

否则返回 recursiveFind(x, head.next, head)

我在使用 smatphone 但类似的东西

一些

于 2012-11-27T01:54:55.400 回答
0

自从我不得不使用 java 和链表（并且在没有测试的情况下从头顶写下）以来已经有一段时间了，所以这可能无法复制/粘贴，但尝试这样的事情：

Node linkedListHead = ...;

public void find(int target){
    Node foundNode = findRec(target, linkedListHead, null);

    if(foundNode != null){
        // assumes Node takes in the Data first, then a Node
        linkedListHead = new Node(target, linkedListHead);
        foundNode.next = foundNode.next.next;
    }
}

private void findRec(int target, Node currentNode, Node previousNode){

    if(currentNode == null){
        return null;

    } else if(currentNode.data == target){
        return previousNode;

    } else {
        return find(target, currentNode.next, currentNode);
    }
}

关键是在 findRec() 方法期间保持对前一个节点的引用并将其返回，以便之后的下一个节点（包含搜索目标）并从列表中删除。

于 2012-11-27T01:57:49.913 回答