C++程序 打印链表倒数第N个节点
给定一个链表和一个数n,编写一个函数,返回链表倒数第n个节点的值。
例如,如果输入如下列表和n = 3,则输出为“B”
方法1(使用链表长度):
- 计算链表的长度。将长度记为len。
- 打印链表开头的第(len – n + 1)个节点。
双指针概念: 第一个指针用于存储变量的地址,第二个指针用于存储第一个指针的地址。如果我们希望通过函数改变变量的值,就把指针传递给它。如果我们希望改变指针的值(即它应该开始指向其他东西),我们就传递指向指针的指针。
以下是上述方法的实现:
// C++ program to find n'th node from
// end
#include <bits/stdc++.h>
using namespace std;
// Link list node
struct Node
{
int data;
struct Node* next;
};
/* Function to get the nth node from
the last of a linked list*/
void printNthFromLast(struct Node* head,
int n)
{
int len = 0, i;
struct Node* temp = head;
// count the number of nodes in
// Linked List
while (temp != NULL)
{
temp = temp->next;
len++;
}
// check if value of n is not
// more than length of the
// linked list
if (len < n)
return;
temp = head;
// get the (len-n+1)th node from
// the beginning
for (i = 1; i < len - n + 1; i++)
temp = temp->next;
cout << temp->data;
return;
}
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list of the
// new node
new_node->next = (*head_ref);
// Move the head to point to
// the new node
(*head_ref) = new_node;
}
// Driver Code
int main()
{
// Start with the empty list
struct Node* head = NULL;
// Create linked 35->15->4->20
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
printNthFromLast(head, 4);
return 0;
}
输出:
35
void printNthFromLast(struct Node* head, int n)
{
int i = 0;
if (head == NULL)
return;
printNthFromLast(head->next, n);
if (++i == n)
cout<<head->data;
}
时间复杂度: O(n),其中n为链表长度。
空间复杂度: O(1),因为使用常量空间进行指针操作。
方法2(使用两个指针):
维护两个指针——参考指针和主指针。将参考指针和主指针都初始化为头部。首先,将参考指针移动到距离头部n个节点。现在一次移动两个指针,直到参考指针到达末尾。现在主指针将指向倒数第n个节点。返回主指针。
以下是上述方法的实现:
以下是上述方法的演示:
以下是上述方法的实现:
// C++程序,用于查找链表倒数第n个结点
# include<bits/stdc++.h>
using namespace std;
/* 链表结点 */
struct Node
{
int data;
struct Node* next;
};
/* 找到链表倒数第n个结点的函数*/
void printNthFromLast(struct Node *head, int n)
{
struct Node *main_ptr = head;
struct Node *ref_ptr = head;
int count = 0;
if(head != NULL)
{
while( count < n )
{
if(ref_ptr == NULL)
{
printf("%d is greater than the no. of "
"nodes in list", n);
return;
}
ref_ptr = ref_ptr->next;
count++;
} /* 结束while循环*/
if(ref_ptr == NULL)
{
head = head->next;
if(head != NULL)
printf("从后数第%d个结点为%d ", n, main_ptr->data);
}
else
{
while(ref_ptr != NULL)
{
main_ptr = main_ptr->next;
ref_ptr = ref_ptr->next;
}
printf("从后数第%d个结点为%d ", n, main_ptr->data);
}
}
}
// 插入一个结点
void push(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 main()
{
/* 空链表 */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
printNthFromLast(head, 4);
}
输出
从后数第4个结点为35
时间复杂度: O(n),其中n为链表长度。
空间复杂度 :O(1),因为使用常量空间。