Danh sách liên kết đệ quy trong Java

Question

Tôi đang làm việc trên một bài tập mà tôi đã viết một chương trình java để in ra theo thứ tự ngược lại dữ liệu chứa trong một danh sách liên kết bằng cách sử dụng đệ quy. Cho đến nay đây là những gì tôi có, nó hoạt động nhưng chỉ trên phần tử cuối cùng trong danh sách IE. nó dừng lại khi nó in phần tử cuối cùng.

public String reverse(IntNode head){ 
     String result = ""; 
     if(head.getLink() == null){ 
      result += head.getData(); 
      return result; 
     } 

     else if(head.getLink().getLink() == null){ 
      result += head.getLink().getData(); 
      head.removeNodeAfter(); 
      return result; 
     } 

     else{ 
      return reverse(head.getLink()); 
     } 
    } 

Làm cách nào để tiếp tục đi qua danh sách ngược lên cây đệ quy?

Answer 1

Mã này phức tạp hơn mức cần thiết. Trong trường hợp này đệ quy có thể được chia thành 2 trường hợp (hoặc 2 con đường thực hiện các chức năng có thể có):

1. trường hợp đệ quy: con đường này tự gọi mình nên đệ quy có thể bắt đầu (hoặc tiếp tục)
2. trường hợp cơ sở: con đường này kết thúc đệ quy bằng cách trả lại mà không tự xưng là

mã của bạn có 2 trường hợp cơ sở, và nó chỉ cần 1. Hãy suy nghĩ về tất cả các đầu vào khác nhau, bạn có thể gọi hàm với:

1. head là null

2. head là một IntNode:

   a. head.getLink() trả về null

   b. head.getLink() trả về một IntNode:

   1. head.getLink().getLink() lợi nhuận null

   2. head.getLink().getLink() trả về một IntNode

Bạn sẽ bắt đầu nhận thấy một mô hình; khi nó đã được đơn giản hóa có thực sự chỉ có 2 đầu vào có thể:

1. head là null
2. head là một IntNode

Nếu head là một IntNode, hàm có thể gọi chính nó với head.getLink() (trường hợp đệ quy) và nó chỉ có thể là 2 đầu vào tương tự, và điều này tiếp tục cho đến khi head trở thành null (trường hợp cơ bản).

---

Để trả lời câu hỏi thực tế của bạn, nó chỉ trả về giá trị yếu tố cuối cùng bởi vì trong trường hợp đệ quy, bạn không thực sự thêm vào trước giá trị của hiện tại IntNode (ví dụ:head.getData()); bạn vừa trả về kết quả của cuộc gọi reverse() tiếp theo, điều đó có nghĩa là cuộc gọi sẽ được chấp nhận cho đến khi nó đến phần tử cuối cùng và trả lại chỉ giá trị của phần tử đó.

Answer 2

Khi suy nghĩ về đệ quy, đó là một chiến lược tốt để xây dựng từ mặt đất, cho đến khi bạn nhấn trường hợp thú vị. Tại mỗi bước, hãy thử sử dụng lại các trường hợp trước đó.

Q1. Đảo ngược danh sách trống là gì? []

A1. Danh sách trống. []

---

Q2. Đảo ngược danh sách với một phần tử đơn lẻ là gì? [1]

A2. Cùng một danh sách. [1]

---

Q3. Đảo ngược danh sách với hai yếu tố là gì? [1 2]

A3. Phần tử đầu tiên, được thêm vào phần tử thứ hai. [2 1] (Bắt đầu thú vị)

---

Q4. Đảo ngược danh sách với ba yếu tố là gì? [1 2 3]

A4. Phần tử đầu tiên được nối vào danh sách các phần tử còn lại. [3 2] + [1] = [3 2 1]

---

Bây giờ mô hình nên bắt đầu để được rõ ràng: sự đảo ngược của một danh sách các yếu tố N là đảo ngược của N cuối cùng - 1 yếu tố với phần tử đầu tiên được thêm vào).

Trường hợp cơ bản của chúng tôi là gì? Từ trên, nó xuất hiện có một danh sách gồm 1 hoặc 0 phần tử. Nhìn kỹ hơn, áp dụng mẫu của chúng ta vào danh sách độ dài 1, chúng ta thấy rằng [1] đảo ngược là [] với phần tử đầu tiên được nối thêm, tức là [] + [1]. Vì vậy, thực sự, trường hợp cơ sở của chúng tôi chỉ là danh sách trống.

Answer 3

Như những người khác đã chỉ ra, giải pháp của bạn phức tạp hơn mức cần thiết.

Trước tiên, lưu ý rằng bạn không cần (và có thể không muốn) loại bỏ bất kỳ mục nào khỏi danh sách để duyệt qua nó. Thứ hai, thay vì kiểm tra nếu liên kết của nút hiện tại là null, bạn thực sự có thể kiểm tra xem chính liên kết hiện tại là null hay không (không có gì sai với điều đó miễn là bạn không cố gắng dereference nó). Điều này đơn giản hóa logic.

public String reverse(IntNode head) { 
    if (head == null) 
     return ""; 
    else 
     return reverse(head.getLink()) + head.getData(); 
} 

Hoặc thậm chí bạn có thể viết nó như thế này:

public String reverse(IntNode head) { 
    return (head == null)? "" : reverse(head.getLink()) + head.getData(); 
}