給定一個單鍊錶和正整數 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 個最後一個節點的指針,頭為第一個節點。
採用靜態計數變數。
取 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中文網其他相關文章!