rust函數遞歸在14中已經提到，接下來我們把206.反轉鏈表，用遞歸法實現
遞歸函數通常包含兩個主要部分：
????????基準條件（Base Case）：遞歸終止的條件，避免無限遞歸。
????????遞歸步驟（Recursive Step）：將問題分解為更小的子問題，并調用自身來解決這些子問題。
//Definition for singly-linked list.#[derive(PartialEq, Eq, Clone, Debug)]pub struct ListNode {pub val: i32,pub next: Option<Box<ListNode>>}impl ListNode {#[inline]fn new(val: i32) -> Self {ListNode {next: None,val}}}pub fn reverse(mut pre : Option<Box<ListNode>>,mut cur : Option<Box<ListNode>>) -> Option<Box<ListNode>> {if let Some(mut node) = cur.take() {//如果不為空使用temp先保存node.next, 然后讓node.next指向prelet mut temp = node.next;node.next = pre;//遞歸調用return reverse(Some(node), temp); } else {pre}
}
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {let mut pre: Option<Box<ListNode>> = None;return reverse(pre, head);
}// 輔助函數：打印鏈表內容不轉移所有權
fn print_list(head: Option<&Box<ListNode>>) {match head {Some(node) => {let mut current = Some(node); // 初始化當前節點指針while let Some(node) = current {print!("{} -> ", node.val);current = node.next.as_ref(); // 使用 as_ref() 獲取對 next 的引用}println!("None");}None => {println!("鏈表為空");}}
}// 函數：將 i32 數組轉換為鏈表并返回頭節點
fn array_to_list(arr: Vec<i32>) -> Option<Box<ListNode>> {let mut head: Option<Box<ListNode>> = None;let mut current: &mut Option<Box<ListNode>> = &mut head;for &val in arr.iter().rev() { // 從后往前構建鏈表let new_node = Box::new(ListNode {val,next: current.take(), // 取出當前節點并設置為新節點的 next});*current = Some(new_node); // 更新當前節點current = &mut head; // 指向頭節點}head
}fn main() { let arr = vec![1, 2, 3, 4, 5];// 調用函數創建鏈表let head = array_to_list(arr);// 打印鏈表print_list(head.as_ref()); // 使用 as_ref() 避免轉移所有權let node = reverse_list(head);print_list(node.as_ref());}
總結，用遞歸首先需要確定終止條件，在翻轉鏈表中，終止條件就是cur為空，然后返回pre， 如果不為空先保存node.next(cur.next)到臨時變量temp中,然后node.next=pre，最后遞歸直到為空返回
)
