C++程序编程写一个获取链表中第N个节点的函数

编写一个GetNth()函数，该函数接受一个链表和一个整数索引，并返回存储在该索引位置上的节点中的数据值。

例如：

输入: 1->10->30->14, index = 2
输出: 30
在索引为2的节点是30。

算法：
1. 初始化count=0
2. 遍历链表
a. 如果count等于传递的索引，则返回当前节点
b. 增加count
c. 将当前节点改变为指向当前节点的下一个节点。

实现：

// C++ program to find n'th
// node in linked list
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
 
// 链表节点
class Node
{
    public:
    int data;
    Node* next;
};
 
/* 给定一个指向链表头的引用（指向指针）和一个 int，在列表的前面加入一个新节点。 */
void push(Node** head_ref,
          int new_data)
{
    // 分配节点
    Node* new_node = new Node();
 
    // 放入数据
    new_node->data = new_data;
 
    // 将新节点的旧列表连接起来
    new_node->next = (*head_ref);
 
    // 将头指向新节点
    (*head_ref) = new_node;
}
 
// 这个函数接受链表的头指针和索引作为参数，并返回索引处的数据
int GetNth(Node* head, int index)
{
    Node* current = head;
 
    // 我们目前正在查看的节点的索引
    int count = 0;
    while (current != NULL)
    {
        if (count == index)
            return (current->data);
        count++;
        current = current->next;
    }
 
    /* 如果我们到达了这条线，
    调用者询问的是一个不存在的元素，
    所以我们断言失败 */
    assert(0);
}
 
// 主函数
int main()
{
    // 从空列表开始
    Node* head = NULL;
 
    // 使用push()函数构造链表
    // 1->12->1->4->1
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);
 
    // 检查计数函数
    cout << "在索引为3处的元素是 " <<
              GetNth(head, 3);
    return 0;
}
// 本代码由rathbhupendra提供```

输出:

在索引为3处的元素是4

时间复杂度： O(n)

空间复杂度： O(1)，只使用恒定变量

方法2-使用递归：

算法：

getnth(node,n)
1. 初始化count=0
2. if count==n
     return node->data
3. else    return getnth(node->next,n-1)

实现：

// C++程序用于使用递归查找链表中的n个节点
#include <bits/stdc++.h>
using namespace std;
 
//链接列表节点
struct Node
{
    int data;
    struct Node* next;
};
 
/*假如一个引用(指向指针)
    到列表头，并使用int，推一下
    列表的前面一个新节点。*/
void push(struct Node** head_ref,
          int new_data)
{
    //分配节点
    struct Node* new_node =
           (struct Node*)malloc(sizeof(struct Node));
 
    //输入数据
    new_node->data = new_data;
 
    //连接新节点的旧列表
    new_node->next = (*head_ref);
 
    //将头移动到新节点
    (*head_ref) = new_node;
}
 
/*以链表的头指针为参数
  和索引，返回索引处的数据。
  (不使用其他变量)*/
int GetNth(struct Node* head, int n)
{
    //如果列表的长度小于
    //给定的索引，返回-1
    if (head == NULL)
        return -1;
 
    //如果n等于0，返回节点->数据
    if (n == 0)
        return head->data;
 
    //将头指针增加到下一个指针
    // n-1:减少次数
    //递归，直到n = 0
    return GetNth(head->next, n - 1);
}
 
//驱动代码
int main()
{
    //从空列表开始
    struct Node* head = NULL;
 
    //使用push()构建列表
    // 1->12->1->4->1
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);
 
    //检查计数函数
    printf("Element at index 3 is %d",
            GetNth(head, 3));
    getchar();
}

输出：