Özyineli Bağlantılı Liste. Neyi yanlış yapıyorum?

Question

public class Reverse { 

    public static void printLL(Node head) { 
     while(head!=null){ 
      System.out.print(head.getData()+"-->"); 
      head=head.next; 
     } 
    } 

    public static Node reverseLL(Node head){ 
     if(head == null) { 
      return head; 
     } 
     return reverseLL(head.next); 
    } 

    public static void main(String[] args) { 
     Node first=new Node(10); 
     Node head=first; 
     Node second=new Node(20); 
     first.next=second; 
     Node third=new Node(30); 
     second.next=third; 
     Node fourth=new Node(40); 
     third.next=fourth; 
     printLL(head); 
     System.out.println("\nReverse of Linked List is \n"); 
     head=reverseLL(head); 
     printLL(head); 
    } 
} 

İşte kodum. Hiçbir şey yazdırmıyor.

Özyinelemeden dolayı, boş göstericiyi işaret ediyor ve bu nedenle boş konumda hiçbir veri yok.

Lütfen kodu doğru yapmak için neler yapabileceğimi söyle. peşin

Answer 1

sorunun

teşekkürler reverseLL yinelemeli Kendisine sonra head için hiçbir şey olmamasıdır.

Temel durum doğru: headnull olduğunda, null'u döndürürsünüz. Ancak, yinelemeli adım tamamlanmadı: listenin geri kalanını geri almanız gerekir, ancak daha sonra onu head'a eklemeniz gerekir. Eğer özyinelemeli yöntem içinde

head.next = prior; 

yapabileceğini böylece

Bunu gerçekleştirmek için en basit yolu, prior düğüm için ekstra bir parametre geçmektir. o özyinelemeli değildir

public static Node reverseLL(Node head) { 
    if(head==null){ 
     return null; 
    } 
    return reverseLL(head, null); 
} 

Not o - öyle hepsi iki argüman aşırı çağırıyor: İşte "sarıcı" yöntemi nasıl görüneceğini olduğunu.

yinelemeli metod head hiç null olduğunu bilir, yani taban durumda head.next == null olduğu: head düğümün ters return önce atama yapılır

public static Node reverseLL(Node head, Node prior) { 
    Node res; 
    if (head.next == null) { 
     res = head; 
    } else { 
     res = reverseLL(head.next, head); 
    } 
    head.next = prior; 
    return res; 
} 

. Yöntem, zincirdeki son olmayan null düğümü nasıl döndürür.

Demo

Answer 2

Sizin reverseLL basitçe tüm Düğümler geçer ve onu if(head==null) yapıyor sonuncusu ulaştığında, null döndürülür.

reverseLL işlevini onarmanız gerekir. Adım adım ne olduğunu anlamak için işleve izler eklemeyi deneyin.

Answer 3

Özyineleme konusunda önemli bir noktayı kaçırmış görünüyorsunuz - kendinizi aramak zorundasınız.

printLL için çalışması gereken bir yinelemeli çözüm göstermesi gereken bir değişiklik önereceğim. kod temelde bir kafa varsa diyor nasıl

public static void printLL(Node head) { 

    if (head != null) { 
     System.out.print(head.getData() + "-->"); 
     printLL(head.next); 
    } 
} 

Not, bu verilerin bunlar yazdırmak ve sonra head.next var yazdırın.