如果元素已被搜索，则重新排序单个链表？

Question

public class SearchLinkedList<E> {
    private Node<E> first;

    public static void main(String[] args){
     SearchLinkedList<Integer> list = new SearchLinkedList<Integer>();
     
     list.insert(1000);
     list.insert(2000);
     list.insert(3000);
     
     System.out.println(list.getFirst());
   }

    public SearchLinkedList() {
      first = null;
   }

    public void insert(E e) {
        if (first == null) {
            first = new Node<E>(e);
        } else {
            //while(temp.next.searched == true) then insert new Node where the next node is null or searched == false
            Node<E> temp = new Node<E>(e);
            temp.next = first;
            first = temp;
        }
    }
    
    public E getFirst() {
        return first.data;
    }

    public E find(E x) {
        if (first == null) {
            return null;
        } else {
            //while (temp != null) if node found set it's searched = true and move it to front of list
            Node<E> temp = first;
            while (temp != null) {
                if (temp.data.equals(x)) {
                    temp.searched = true;
                    return temp.data;
                }
                temp = temp.next;
            }
            return temp.data;
        }
    }

    private static class Node<E> {
        private E data;
        private boolean searched;
        private Node<E> next;

        private Node(E e) {
            data = e;
            searched = false;
            next = null;
        }
    }
}

因此，这里的任务是创建一个LinkedList类，如果已经搜索了节点，它会将节点移动到列表的前面（第一个）。这里的第一张图片是当它被调用时：

list.insert(1000);
list.insert(2000);
list.insert(3000);

第二个图像是当这被称为：

list.find(3000);
list.find(2000);

所以目标是在调用find并找到包含数据的节点时：将其搜索布尔值设置为true，并将该节点移动到列表的前面。到目前为止，我的insert只是将新节点放在列表的前面。insert and find中的注释解释了我想让它们做什么。然而，将一个元素从单个linkedlist的中间移动到前面似乎很难。我不知道该怎么办。你可以自己复制并尝试。调用列表后。find（2000年） 然后是列表。getFirst（）我们应该得到2000美元。问题是如何。。。我的想法是，我是否应该让节点的布尔值决定是否在前方。。。我一点也不确定。




Answer 1

我想你应该这样做：

public class SearchLinkedList<E> {
private Node<E> first;

public static void main(String[] args) {
    SearchLinkedList<Integer> list = new SearchLinkedList<Integer>();

    list.insert(1000);
    list.insert(2000);
    list.insert(3000);

    System.out.println(list.getFirst());

    System.out.println(list.find(3000));
    System.out.println(list.getFirst());
    list.insert(4000);
    System.out.println(list.find(200));
}

public SearchLinkedList() {
    first = null;
}

public void insert(E e) {
    if (first == null) {
        first = new Node<E>(e);
    } else {
        //while(temp.next.searched == true) then insert new Node where the next node is null or searched == false
        Node<E> temp = first;
        while (temp.next != null && temp.next.searched) {
            temp = temp.next;
        }
        Node<E> node = new Node<>(e);
        if (temp.next != null) {
            node.next = temp.next;
        }
        temp.next = node;
    }
}

public E getFirst() {
    return first.data;
}

public E find(E x) {
    if (first == null) {
        return null;
    } else {
        //while (temp != null) if node found set it's searched = true and move it to front of list
        Node<E> temp = first;
        while (temp != null) {
            if (temp.data.equals(x)) {
                temp.searched = true;
                break;
            }
            temp = temp.next;
        }
        if (temp == null) return null;

        pushForward(temp);
        return temp.data;
    }
}
//Find pre-linked node with our node, bind our node with parent next node
//and link parent with node.
private void pushForward(Node<E> node) {
    if (first == null || first.next == null) return;
    Node<E> temp = first;
    while (temp.next != null) {
        if (temp.next.equals(node)) {
            temp.next = temp.next.next;
            node.next = first;
            first = node;
            break;
        }
        temp = temp.next;
    }
}

private static class Node<E> {
    private E data;
    private boolean searched;
    private Node<E> next;

    private Node(E e) {
        data = e;
        searched = false;
        next = null;
    }
}

}

你也可以混合使用pushForward和find方法，通过列表（O（n））中的一次迭代，让find做你想做的事情，因为那里有O（n^2）。可能会有帮助：https://www.geeksforgeeks.org/java-program-for-inserting-node-in-the-middle-of-the-linked-list/