使用遞歸方法在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中文網其他相關文章！