java - 删除链表中出现多次的每个元素的第一次出现

Question

编写方法removeFirst(LinkedList 类的成员)，用于删除列表中多次出现的每个元素的第一个匹配项。不使用任何辅助数据结构，也不调用任何方法。方法签名是 public void removeFirst()。

示例 4.1。如果列表包含:B => A => A => R => C => A => C => R，则 调用removeFirst后，其内容变为B => A => A => C => R。

我将其作为 Arraylist 类的成员来解决，并使用了辅助数据结构。

public void removeFirst() {

Node<T> traverse = head;

        int[] array = new int[10];
        int[] repeat = new int[10];
        int count=0;
        int rcount=0;

        boolean isAlready = false;

        while (traverse!=null)
        {
            for (int i=0; i<count; i++)
            {
                if (array[i]==traverse.value)
                {
                    isAlready=true;
                    break;
                }
            }

            if(!isAlready)
                array[count++] = traverse.value;
            else
                repeat[rcount++] = traverse.value;

            traverse = traverse.next;
        }

        traverse= head;
        while (traverse!=null)
        {
            for (int i=0; i<rcount; i++)

            traverse=traverse.next;
        }

    }//

知道如何在不使用任何辅助数据结构的情况下作为 LikedList 类的成员来解决这个问题，您可以使用的就是

public class Node<T> {
public T data;
public Node<T> next;
public Node () {
data = null;
next = null;
}
public Node (T val) {
data = val;
next = null;
}
// Setters/Getters...
}//End of class Node

public class LinkedList<T> { //LinkedList class
private Node<T> head;
private Node<T> current;
public LinkedList () {
head = current = null;
}

Answer 1

我在学习数据结构类(class)时遇到了这个问题，这有点难，但这就是我所做的。

public void removeFirst() {
    int counter = 0 ;
    Node<T> tmp = null ; 
    Node<T> comp = head ; 
    current = head ;
    Node<T> secHead = null ;
    Node<T> secCurr = null ; 
    boolean check = false ;
    boolean control = true ;
    while(current.next != null || current == null) {
        counter = 0 ; 
        comp = head ;
        while(comp.next != null) { // we iterate using node through original list to check for occurences 
            if(comp.data == current.data) {
                counter++;
            }

            comp = comp.next ; 
        }
        if(comp.data == current.data) {
            counter++;
        }
        tmp = current ;
        if(counter >= 2) { 
            check = false ;
            secCurr = secHead ;
            while(secCurr != null) { // check for deleting to avoid multiple deletes  

                if(tmp.data.equals(secCurr.data)) {
                    check = true ;
                    break ;
                }
                secCurr = secCurr.next ;
            }
            secCurr = secHead ;
            if(!check) { // deleting and adding to our secondary linkedlist to check it later :)
                remove();
                control = false ;
                Node<T> tmp2;
                if (secHead == null) {
                    secHead = new Node<T> (tmp.data);
                    secCurr = secHead ;
                }
                else {
                    tmp2 = secCurr.next;
                    secCurr.next = new Node<T> (tmp.data);
                    secCurr = secCurr.next;
                    secCurr.next = tmp2;
                }
            }


        }
        if(control) { // remove() increment the current this is for checking 
            current = current.next ;
        }
        control = true ;

    }
}

通过使用类节点的属性，您可以创建辅助 LinkedList，但不使用类本身，因此我们从未使用辅助数据结构。你需要知道内部方法具体是如何工作的。仔细阅读代码:)