0

JavaのLinkedListからアイテムを削除しようとしています。このリストは私によって実装されており、JavaAPIを使用していません。私が直面している主な問題は、再帰コーディングで常に迷子になっているRECURSIONにあります。

class List{

    int N;
    List next;
    List current;
    List(int N){
        this.N =N;
        this.next = null;
    }

    @Override
    public String toString() {
        String o = "";
        List curr = this;
        while(curr != null){
            o += curr.N+"-->";
            curr = curr.next;
        }

        return o+"TAIL";
    }
}

実装されたメソッド：

private static List Remove(List L,int N){
    if(L == null || L.next == null)
        return L;

    List current = L;
    List previous = null;

    while(current != null){
        if(current.N == N){
            current = current.next;
            if(previous == null)previous = current;
            else{
                previous.next = current;
            }
            break;
        }else{
            previous = current;
            current = current.next;             
        }   
    }
    return previous;
}

入力-

List list1 = new List(1);
        list1.next = new List(2);
        list1.next.next = new List(3);
        list1.next.next.next  = new List(4);
        list1.next.next.next.next  = new List(5);
        list1.next.next.next.next.next  = new List(6);
        list1.next.next.next.next.next.next  = new List(7);
System.out.println("Before Removal "+list1.toString());
        System.out.println("After Removal "+Remove(list1,3));

私が得ている出力は-

  • 取り外し前1->2->3-> 4-> 5--> 6 ---> 7-> TAIL
  • 取り外し後2->4->5-> 6 ---> 7-> TAIL

current = current.nextここで、または参照が次の値に設定されているため、値1が失われています。したがって、間違いなく、さまざまな参照に保存されているデータの表示に問題があります。

4

2 に答える 2

2

間違いはここにあります：

return previous;

リストが削除されていない場合は、リストの元の先頭を返す必要があります。グラフィカルに表示するには：

N == 3
List Before Removal: 1-->2-->3-->4-->5-->6-->7-->TAIL
At start of iteration 1:
L                    ^
previous      (null)
current              ^
No match -> iteration 2:
L                    ^
previous             ^
current                  ^
No match -> iteration 3:
L                    ^
previous                 ^
current                      ^
Match -> remove current:
List After Removal:  1-->2-->4-->5-->6-->7-->TAIL
L                    ^
previous                 ^
current                      ^

この時点で、を返すpreviousと、前のヘッド要素が失われますL。

ヘッド要素を削除する場合は、ループの前に別のチェックを追加する必要があります。

ところで、あなたのRemoveメソッドは再帰的ではありません-それ自体を呼び出すことは決してありません。

于 2012-04-25T09:17:51.597 に答える
1

これは、単にヘッドを返さないためです。代わりに、「削除した」ノードへの前のポインタを返します。

static List Remove(final List L, final int N) {
    // Base case for null head pointer  
    final List head = L;
    if (head == null)
        return head;

    // Base case for removing the head
    if (head.N == N)
       return head.next;

    List current = head.next;
    List previous = head;

    while (current != null) {
        if (current.N == N) {
            current = current.next;
            if (previous == null) {
                previous = current;
            }
            else {
                previous.next = current;
            }

            break;
        } else {
            previous = current;
            current = current.next;
        }
    }

    return head;
}

また、明確にするために、これは再帰的な解決策ではありません。

于 2012-04-25T09:23:44.650 に答える