联系
本程序实现单链表的一些稍微高级一点的操作：
- 查找单链表倒数第n个元素的值
- 查找单链表中间元素的值(中间值可能有两个)
- 一个单向的链表,知道只有一个指向某个节点的指针p，并且假设这个节点不是尾节点，试编程实现删除此节点
4、在查找单链表倒数第n个元素时,有三种方法 第一种是规尺法，即利用两个步长为n的指针,同时前进直至第一个指针到达终点,那么第二个指针所指的对象就是想要得到的值,时间复杂度为O(2N),空间复杂度为0 第二种是构造一个先进先出队列(指针队列),大小为n,遍历单链表,将遍历到的单链表结点的地址逐个存进队列中,直至单链表遍历结束.那么,这个队列的最后一个元素就是想要得到的数据,时间复杂度为O(N),空间复杂度为O(n) 第三种方法可以先逆置该链表,然后顺序取第n个元素作为结果返回,最后再次逆置链表时间复杂度为O(3N),空间复杂度为0
5、用最快的方法求出单链表中间的元素 用二个指针,一开始同时指向链表头,然后同时往后走,第一个指针走二步,第二个指针走一步,那么,当第一个指针走到头时,第二个指针所指向的就是需要返回的值。当单链表元素个数为单数,中间元素值其实是有二个.可以通过这样来判断:当第一个指针走二步刚好是NULL,则说明单链表有偶数个元素,则应该返回二个中间值当第一个指针走一步刚才是NULL,则说明单链表有奇数个元素,则应该返回一个中间值。
6、一个单向的链表,知道只有一个指向某个节点的指针p，并且假设这个节点不是尾节点， 试编程实现删除此节点. 此问题,可以将p下面的那个结点的值赋给p,然后将p的next指针指向下下个结点就可以了. 如: 5->4->3->2->1 要删除4这个结点,那么,我们就将3赋给4,变成了 5,3,3,2,1 然后改变指针的指向, 变成 5,3,[3],2,1 (中括号的表示被删除掉)
程序清单：
//---------------------------------------------------------------------------
// KnightList::FindInverseElemSingleList
//
// 寻找倒数第n个元素
int KnightList::FindInverseElemSingleList(int n,int type)
{
switch(type){
// 第一种方法,用标迟法
case 1:
{
struct KnightNode*p,*q;
p = q = m_singleList->next;
int tmpN = n;
while(1){
if(!tmpN)
break;
if(p==NULL)
break;
p = p->next;
--tmpN;
}
if(tmpN>0)
return -99999; // 没有找到
while(p){
p = p->next;
q = q->next;
}
return q->value;
}
break;
// 用先进先出指针队列实现
case 2:
{
struct KnightNode** pArray;
// 开辟的是指针数组
pArray = new (KnightNode*[n]);
int found = false;
struct KnightNode* p = m_singleList->next;
int i=0;
while(p){
pArray[i] = p;
p = p->next;
// 这里有个问题
// 不可写成
/*
if(i>=n){
i=0;
found = true;
}
else{
++i;
}
我们一定要先让i先加起来,再判断这时的i是否有越界
这里很容易出错
*/
++i;
if(i>=n){
i = 0;
found = true;
}
}
if(!found){
// 注意 指针数组需要释放
delete []pArray;
return -9999;
}
int ret = (*pArray[(i)%n]).value;
delete []pArray;
return ret;
}
break;
case 3:
{
ConverseSingleList();
struct KnightNode* p = m_singleList->next;
int tmpN = n;
while(p){
p = p->next;
--tmpN;
// 要减到1,而不是0
/*
这里
if(tmpN==0)
break; 是错的
*/
if(tmpN==1)
break;
}
if(tmpN>1)
return -9999;
int ret = p->value;
ConverseSingleList();
return ret;
}
break;
}
return -99999;
}
//---------------------------------------------------------------------------
// KnightList::FindMiddleSingleList
//
// 寻找中间元素
// ret1 和 ret2是返回的两个中间值
// 本函数返回的值是: 有几个中间值
int KnightList::FindMiddleSingleList(int &ret1,int &ret2)
{
struct KnightNode* p,*q;
p = q = m_singleList->next;
int step = 0;
while(1){
// 第一个指针走
p = p->next;
step= (step+1)%2; // 记录第一个指针最后一次到底是走几步才NULL
if(NULL==p)
break;
p = p->next;
step= (step+1)%2;
if(NULL==p)
break;
// 第二个指针走
q = q->next;
}
ret1 = q->value;
if(step==1){
// 一个中间值
return 1;
}
ret2 = (q->next)->value;
return 2;
}
//---------------------------------------------------------------------------
// KnightList::DeleteNodeSingleList
//
// 删除指定的结点
void KnightList::DeleteNodeSingleList(void *node)
{
if(NULL==node)
return;
struct KnightNode* p = (struct KnightNode*)node;
// 将该元素的值赋为下个元素的值
p->value = p->next->value;
// 然后将该指针指向下下的元素
p->next = p->next->next;
}
本文链接地址：逆置单链表,求单链表中间元素,删除指定结点