首頁  >  文章  >  後端開發  >  使用遞歸方法在C++中找到鍊錶倒數第n個節點

使用遞歸方法在C++中找到鍊錶倒數第n個節點

WBOY
WBOY轉載
2023-09-15 17:53:051109瀏覽

使用遞歸方法在C++中找到鍊錶倒數第n個節點

給定一個單鍊錶和正整數 N 作為輸入。目標是使用遞歸找到給定清單中從末尾算起的第 N 個節點。如果輸入清單有節點 a → b → c → d → e → f 且 N 為 4,則倒數第 4 節點將是 c。

我們將首先遍歷直到列表中的最後一個節點以及從遞歸(回溯)增量計數返回。當 count 等於 N 時,則傳回指向目前節點的指標作為結果。

讓我們看看此的各種輸入輸出場景-

輸入- List : - 1 → 5 → 7 → 12 → 2 → 96 → 33 N= 3

輸出− 倒數第N 個節點為:2

#解釋− 第三個節點是2。

輸入− 列表:- 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

#輸出- 節點不存在。

說明 - 清單只有7 個節點,因此不可能有倒數第8 個節點.

下面的程式中使用的方法如下

在這種方法中,我們將首先使用遞歸到達列表的末尾,在回溯時我們將增加一個靜態計數變數。一旦 count 等於輸入 N,就傳回目前節點指標。

  • 採用帶有 int 資料部分的結構 Node,並將 Node 作為下一個指標。

    • 採用結構 Node 和 int 資料部分。 p>

    • 函數addtohead(Node** head, int data)用於向頭部新增節點,建立單向鍊錶。

    • 使用上面的函數建立單向鍊錶,頭作為指向第一個節點的指標。
    • 函數display(Node* head)用來列印從頭開始的鍊錶

    • 取 N 為正整數。

    • 函數 findNode(Node* head, int n1) 取得指向head 和 n1,當找到倒數第 n1 個節點時列印結果。

    • 將blast當作指向倒數第 n1 個節點的指標。

    • 呼叫 searchNthLast(head, n1, &nlast) 來找出該節點。

    • 函數searchNthLast(Node* head, int n1, Node** nlast) 傳回指向鍊錶中從末尾算起第n1 個最後一個節點的指針,頭為第一個節點。

    • 採用靜態計數變數。

    • 如果 head 為 NULL,則不傳回任何內容。
    • 取 tmp=head->next。

    • 呼叫 searchNthLast(tmp, n1, nlast) 遞歸遍歷直到最後一個節點。

    • 之後 count 加 1。

    • 如果 count 變成等於n1則設定*nlast=head。

    • 最後列印nlast所指向的節點的值作為結果。

    範例

    #include <bits/stdc++.h>
    using namespace std;
    struct Node {
       int data;
       Node* next;
    };
    void addtohead(Node** head, int data){
       Node* nodex = new Node;
       nodex->data = data;
       nodex->next = (*head);
       (*head) = nodex;
    }
    void searchNthLast(Node* head, int n1, Node** nlast){
       static int count=0;
       if (head==NULL){
          return;
       }
       Node* tmp=head->next;
       searchNthLast(tmp, n1, nlast);
       count = count + 1;
       if (count == n1){
          *nlast = head;
       }
    }
    void findNode(Node* head, int n1){
       Node* nlast = NULL;
       searchNthLast(head, n1, &nlast);
       if (nlast == NULL){
          cout << "Node does not exists";
       }
       else{
          cout << "Nth Node from the last is: "<< nlast->data;
       }
    }
    void display(Node* head){
       Node* curr = head;
       if (curr != NULL){
          cout<<curr->data<<" ";
          display(curr->next);
       }
    }
    int main(){
       Node* head = NULL;
       addtohead(&head, 20);
       addtohead(&head, 12);
       addtohead(&head, 15);
       addtohead(&head, 8);
       addtohead(&head, 10);
       addtohead(&head, 4);
       addtohead(&head, 5);
       int N = 2;
       cout<<"Linked list is :"<<endl;
       display(head);
       cout<<endl;
       findNode(head, N);
       return 0;
    }

    輸出

    如果我們執行上面的程式碼,它將產生以下輸出

    Linked list is :
    5 4 10 8 15 12 20
    Nth Node from the last is: 12
    #

以上是使用遞歸方法在C++中找到鍊錶倒數第n個節點的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除

相關文章

看更多