C++程序打印链表倒数第N个节点

给定一个链表和一个数n，编写一个函数，返回链表倒数第n个节点的值。

例如，如果输入如下列表和n = 3，则输出为“B”

C++程序打印链表倒数第N个节点

方法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;
   }

输出：

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个节点

以下是上述方法的实现：

// 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);
}