“链表倒数第K个节点”

题目描述

输入一个链表，输出该链表中倒数第k个结点。
思路：设置两个指针指向头节点分别为p，和ptr；
让p指针先走k-1次，然后让ptr跟着p指针一直遍历下去直到遍历完整个链表，这时ptr指针就指向倒数第k个节点了。
有些兴趣的同学可以仔细琢磨。很有意思。
附上我的代码：

#include<iostream>
using namespace std;

typedef struct Node//链表结构
{
	int data;
	Node* next;
 }Node;

Node* init_list( int n)//初始化链表
{
	Node* head = NULL;
	 if (n < 0)
	 {
		 cout << "链表数目个数有问题" << endl;
	 }
  else if(n == 0)
		{
	  head = NULL;
	  return head;
		}
	else
	{
		cout<< "请输入 " << n << "个数据"<<endl;

		while (n-- > 0)
		{
			Node* ptr = new Node;
			 cin >> ptr->data;
			 ptr->next = head;
			 head= ptr;

		}
	}
  return head;
}
void show(Node *head)//打印链表
 {
	 if (head == NULL)
	 {
		 cout << "这是一个空链表" << endl;
	 }
	 while (head!=NULL)
	 {
		 cout << head->data << "->";
		 head = head->next;
	 }
	 cout << "NULL"<<endl;
 }

 Node*  FindKthToTail(Node* head, int k)//链表节点
  {
 	 if (NULL == head&&k<=0)
 	 {
 		 return NULL;
 	 }
 	 Node* p = head, *ptr = head;
 	 for (int i = 0; i < k-1; i++)
 		 {
 			 if (p->next != NULL)
 			 {
 				 p = p->next;
 			 }
 		 }
 	 while (p->next)
 	 {			
 		 ptr = ptr->next;
 		 p = p->next;	 
 	 }
 	 return ptr;
  }

int  main() //主函数
  {
	// Node*ptr3= create_list();
	// show(ptr3);
	  int n;
	  cout << "请输入你想要创建的链表节点个数" << endl;
	  cin >> n;
	 Node* ptr=init_list(n);
	 show(ptr);
	//insert(ptr,4,5);
    //  show(ptr);
	//Node* ptr2=resevertlist(ptr);
	//show(ptr2);
	// minus_point(ptr2, 2);
	// show(ptr2);
    //	Node*ptr3= minus_point(ptr2, 1);
	// show(ptr3);
	//int count= sort_list(ptr3);
	//cout << count << endl;
	 Node*ptr4 = FindKthToTail(ptr, 3);
	 cout << ptr4->data;
	 return 0;
 }

运行结果：

赏

谢谢你请我吃个糖

支付宝

微信

本文总阅读量次