資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中使用遞迴查詢連結串列中倒數第n個節點
給定一個單鏈表和一個正整數N作為輸入。目標是使用遞迴在給定列表中找到從末尾開始的第N個節點。如果輸入列表的節點為a → b → c → d → e → f，並且N為4，則從末尾開始的第4個節點將為c。
我們首先遍歷到列表的最後一個節點，並在從遞迴返回（回溯）時遞增計數。當計數等於N時，返回指向當前節點的指標作為結果。
讓我們看看這種情況下的各種輸入輸出場景 -
輸入 - 列表：1 → 5 → 7 → 12 → 2 → 96 → 33 N=3
輸出 - 從最後一個節點開始的第N個節點是：2
解釋 - 倒數第3個節點是2。
輸入 - 列表：12 → 53 → 8 → 19 → 20 → 96 → 33 N=8
輸出 - 節點不存在。
解釋 - 列表只有7個節點，因此不可能有第8個最後一個節點。
下面程式中使用的方案如下
在這種方法中，我們將首先使用遞迴到達列表的末尾，並在回溯時遞增一個靜態計數變數。一旦計數等於輸入N，則返回當前節點指標。
使用int資料部分和Node作為下一個指標的結構Node。
函式addtohead(Node** head, int data)用於將節點新增到頭部以建立單鏈表。
使用上述函式建立單鏈表，其中head為指向第一個節點的指標。
函式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為第一個節點。
取一個靜態計數變數。
如果head為NULL，則不返回任何內容。
取tmp=head->next。
呼叫searchNthLast(tmp, n1, nlast)遞迴遍歷到最後一個節點。
之後將計數加1。
如果計數等於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
445 次檢視
