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

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 class 将一个节点移动到列表的前面（第一个），如果它已经被搜索到。这里的第一张图片是在调用时：

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

第二张图片是调用时的：

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

因此目标是在调用 find 并找到包含数据的节点时：将其搜索布尔值设置为 true 并将该节点移至列表前面。截至目前，我的插入只是将新节点放在列表的前面。 insert 和 find 中的注释解释了我想让它们做什么。然而，将一个元素从单个链表的中间移动到前面似乎很难。不知道在这里做什么。您可以自己复制并尝试。在调用 list.find(2000); 然后 list.getFirst() 之后，我们应该得到 2000。问题是如何......我的想法是我是否应该让节点的布尔值决定是否在前面......不确定在这里全部.

感谢 danilllo19 的帮助。这个答案是正确的，唯一的问题是新元素应该从前面添加，所以如果搜索一个元素，我们应该在最后一次搜索之后但在未搜索元素的头部添加新元素。像这样解决：

public void insert(E e) {
    if(first == null){
        first = new Node<E>(e);
    }else{
        Node<E> temp = first;
        while(temp.searched && temp.next != null && temp.next.searched){
            temp = temp.next;
        }
        Node<E> node = new Node<E>(e);
        
        if(temp.searched && temp.next != null && !temp.next.searched){
            Node<E> temp2 = temp.next;
            
            temp.next = node;
            node.next = temp2;
        }else if(temp.searched && temp.next == null){
            temp.next = node;
        }else{
            node.next = temp;
            first = node; 
        }
        
    }
}

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 方法，使 find 通过列表 (O(n)) 的一次迭代来执行您想要的操作，因为 O(n ^2) 那里。可能有帮助：https://www.geeksforgeeks.org/java-program-for-inserting-node-in-the-middle-of-the-linked-list/

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

Re-order single linked list if elements have been searched?

java

linked-list

singly-linked-list