資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中查詢連結串列從中間到頭的第k個節點
在這個問題中，我們給定一個連結串列和一個數字k。我們的任務是從連結串列的中間朝向頭部查詢第k個節點。
讓我們舉個例子來理解這個問題：
輸入：連結串列：4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k = 2
輸出：7
解釋：
中間節點的值是9。
從中間朝向頭部，第2個節點是7。
解決方案
我們需要找到從連結串列中間到開頭的第k個元素。為此，我們需要遍歷連結串列從頭到尾找到連結串列的大小。
從中間到開頭的第k個元素是從開頭數的第(n/2 + 1 - k)個元素。
程式演示了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int findKmiddleNode(struct Node* head_ref, int k) {
int n = 0;
struct Node* counter = head_ref;
while (counter != NULL) {
n++;
counter = counter->next;
}
int reqNode = ((n / 2 + 1) - k);
if (reqNode <= 0)
return -1;
struct Node* current = head_ref;
int count = 1;
while (current != NULL) {
if (count == reqNode)
return (current->data);
count++;
current = current->next;
}
}
int main()
{
struct Node* head = NULL;
int k = 2;
pushNode(&head, 5);
pushNode(&head, 10);
pushNode(&head, 8);
pushNode(&head, 12);
pushNode(&head, 9);
pushNode(&head, 1);
pushNode(&head, 7);
pushNode(&head, 2);
pushNode(&head, 4);
cout<<k<<"th element from beginning towards head is "<<findKmiddleNode(head, k);
return 0;
}輸出
2th element from beginning towards head is 7
更新於：2021年1月25日
374 次瀏覽
廣告