如何将节点链表中的搜索值移动到链表的头部？

Question

我正在尝试编写一个 find(Object x) 方法，如果找到一个存储 Object y.equals(x) 的节点，将该节点移动到链表（自组织列表）的前面。如果找到，方法 returns 被移到前面的节点的值。如果没有找到，return null。

我的节点 inner-class 包含一个 Node<T> next 和一个 Object val。

这是我尝试过的：

public Object find(Object x) {

        //cant find an object that doesnt exist
        if (isEmpty()) {
            return null;
        }

        // store the head
        Node tmp = head;
        //keep track of previous for updating the link if found
        Node prev = null;


        //traverse linked list
        while (tmp!=null) {
            //find x
            if (tmp.val.equals(x)) {
                //update node storing x to be the head
                tmp = head;

                //re-link the LL
                prev.next = tmp.next;

                return head.val;
            }
            //continue traversing if not found
            prev = tmp;
            tmp = tmp.next;
        }
        //x was not found, return null;
      return null;
    } // end find

我的方法没有正确找到对象，但目前我似乎找不到代码有什么问题。是否需要逆序遍历链表才能做到这一点？

Answer 1

if 块没有正确地重新连接您的列表。 tmp = head不会移动一个节点成为头部。你失去 tmp 引用的任何内容。您应该 mutate tmp（而不是分配给它）并指出它的 后继者 将是当前的 head。然后你应该将其推广为 head:

    if (tmp.val.equals(x)) {
        // Only change something when the match is not the current head
        if (prev != null) { 
            // First(!) re-link the LL
            prev.next = tmp.next;
            // Move the node before the current head
            tmp.next = head;
            // Finally, make it the head
            head = temp;
        }
        return head.val;
    }

如何将节点链表中的搜索值移动到链表的头部？

How to move a searched value in a linked list of nodes to the head of the linked list?

java

linked-list

data-structures