연결된 목록 재귀 removeAll 메서드

Question

단일 값으로 연결된 목록에서 대상 값과 동일한 인스턴스를 모두 제거하는 재귀 적 메서드를 정의하려고합니다. 나는 remove 메소드와 함께 removeAux 메소드를 정의했다. 헤드를 제거해야 할 경우 헤드를 재 할당 할 수 있도록 어떻게 변경할 수 있습니까?

public class LinkedList<T extends Comparable<T>> { 

private class Node { 
    private T data; 
    private Node next; 

    private Node(T data) { 
     this.data = data; 
     next = null; 
    } 
} 

private Node head; 

public LinkedList() { 
    head = null; 
} 

public void remove(T target) { 
    if (head == null) { 
     return; 
    } 

    while (target.compareTo(head.data) == 0) { 
     head = head.next; 
    } 

    removeAux(target, head, null); 
} 

public void removeAux(T target, Node current, Node previous) { 
    if (target.compareTo(current.data) == 0) { 
     if (previous == null) { 
      head = current.next; 
     } else { 
      previous.next = current.next; 
     } 
     current = current.next; 
     removeAux(target, current, previous); // previous doesn't change 

    } else { 
     removeAux(target, current.next, current); 
    } 
} 

Answer 1

난 당신이 대답 graphically linked list 당신을 도울 수도 있습니다

public void remove(T target){ 
    removeAux(target,head, null); 
} 


public void removeAux(T target, Node current, Node previous) { 
     //case base 
     if(current == null) 
       return; 

    if (target.compareTo(current.data) == 0) { 

     if (previous == null) { 
      // is the head 
      head = current.next; 
     } else { 
      //is not the head 
      previous.next = current.next; 
     } 
     current = current.next; 
     removeAux(target, current, previous); // previous doesn't change 

    } else { 
     removeAux(target, current.next, current); 
    } 
} 

확인과 같은 다음 일에 이전 전환 제거 할 때 이전에 대한 참조를 전달하는 것을 선호 : 여기에 지금까지 무엇을 가지고 그것을 구현하는 방법을 생각해보십시오. 훈련 용으로 좋지만 반복적으로 할 수있는 경우.

Answer 2

이렇게하면 작동하도록 함수를 멋지게 만들 수 있습니다.

head = removeAux(target, head); // returns new head 

Coursera 's Algorithms 클래스에서 알 수없는 멋진 트릭.

나머지 코드는 다음과 같습니다.

public void removeAux(T target, Node current) { 
    //case base 
    if(current == null) 
      return null; 

    current.next = removeAux(target, current.next); 

    return target.compareTo(current.data) == 0? current.next: current; // the actual deleting happens here 
}