节点的构造

?

#include
  
   
using namespace std;

template
   
     class list; template
    
      class list_node { friend class list<_Ty>; public: list_node():next(NULL) {} list_node(const _Ty item, list_node<_Ty>* tail=NULL):data(item),next(tail) {} ~list_node() {} private: _Ty data; list_node *next; };
    
   
  

?

?

#include "list_node.h"

template
  
   
class list
{
public:
	list():head(new list_node<_Ty>())
	{
	}
	~list()
	{
		delete head;
	}
public:
	void Insert(const _Ty x,int i)//将数据x插入到位置i之后
	{
		list_node<_Ty> *phead = head;
		list_node<_Ty> *p = new list_node<_Ty>(x);
		while(--i && phead)
		{
			phead = phead->next;
		}
		p->data = x;
		p->next = phead->next;
		phead->next = p;	
	}
	void Show()const
	{
		list_node<_Ty> *phead = head->next;
		while(phead != NULL)
		{	
			cout<
   
    data<<"->"; phead = phead->next; } cout<
    
      *p = head->next; while(--i) { p = p->next; } return p->data; } _Ty Remove(int i) //删除i位置的节点，返回被删除节点的data。 { list_node<_Ty>* p = head; list_node<_Ty> *q; while(--i && p) { p = p->next; } q = p->next; p->next = q->next; _Ty tmp = q->data; delete q; return tmp; } void RemoveAll(_Ty item) //删除所有p->data==item的节点 { list_node<_Ty> *p = head->next; int i = 1; while(p != NULL) { if(p->data == item) { p = p->next; //记录p的下一个节点，下次从p->next处开始查询 Remove(i); } else { i++; p = p->next; } } } void Clear() { list_node<_Ty>* p = head->next; while(p != NULL) { p = p->next; Remove(1); } } size_t size()const //不加head节点 { int i = 0; list_node<_Ty> *p = head->next; while(p != NULL) { i++; p = p->next; } return i; } private: list_node<_Ty> *head; }; 
    
   
  

?

//测试实例

?

#include "list.h"

void main()
{
	list
  
    st;
	for(int i=1; i<10; ++i)
		st.Insert(i,i);
//	st.Insert(5,5);
//	st.Insert(2,2);
//	st.Show();
//	st.Remove(2);
//	st.Show();
//	st.RemoveAll(2);
	cout<
   
     面试宝典中---查找单链表的倒数第K个元素
    
?
    
实现思路主要有三个：
    
1、使用两个指针fast和slow遍历，让fast先遍历K个节点，此时fast和slow同时遍历，当fast遍历到NULL节点时，即为所求 --->（此方法只遍历一次）
    
?
    
_Ty Find2(int K)
{
	list_node<_Ty> *fast = head->next;
	list_node<_Ty> *slow = head->next;
	while(K--)
	{
		fast = fast->next;
	}
	while(fast != NULL)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->data;
}
 2、首先遍历所有节点统计节点个数size，要查找倒数第K个元素，即为查找正数第size-K+1个元素。在重新遍历到suze-K+1位置处即可。 
    
?
 
    
?
 
    
_Ty Find(int K) //找出倒数第K个元素
{
	list_node<_Ty> *p = head->next;
	int i = 1;
	while(p->next != NULL)
	{
		i++;  //统计总的元素个数
		p = p->next;
	}  
	int j = i-K+1;  //相当于查找第j个元素
	p = head->next;
	while(--j && p!=NULL)
	{
		p = p->next;
	}
	return p->data;
}
 3、使用两个指针，一个负责遍历，一个记录遍历前节点的指针；首先遍历K个节点，判断当前节点是否为空， 
    
?
 
    
若为空，则说明遍历前节点（即首节点为所求）；若不为空，记录指针指向下一个节点，赋给遍历指针，遍历指针继续遍历K个节点，依次类推...
 
    
_Ty Find3(int K)
{
	list_node<_Ty> *p = head->next;
	list_node<_Ty> *q = head->next;
	while(p != NULL)
	{
		while(K--)
		{
			p = p->next;
		}
		if(p == NULL)
			return q;
		else
		{
			q = q->next;
			p = q;
		}		
	}	
}
 
    
 
    
 
    
?