问题：假设一个没有头指针的单链表。一个指针指向此单链表中间的一个节点（既不是第一个，也不是_天蝎座的moonlight_新浪博客
问题：假设一个没有头指针的单链表。一个指针指向此单链表中间的一个节点（既不是第一个，也不是
firee(p-&next);&
链表结点定义如下：
struct ListNode
ListNode* m_pN
解答：假设给定的指针为pCurrent，ListNode* pNext =
pCurrent-&m_pNext；
由题意知，pCurrent指向链表的某一个中间节点，因此pCurrent-&m_pNext !=
要删除pCurrent指向的节点B很简单，但必须将节点B前后两个节点A和C连接起来，但是单链表节点没有头指针，因此无法追溯到A，也就无法将A和C相连了。
无法删除节点B，但我们可以删除B的后继节点C，并通过pCurrent-&m_pNext =
pCurrent-&m_pNext-&m_pNext重新将链表连接起来，而唯一丢失的是节点C的数据项m_nKey。因此，我们只需要将节点C的数据项取代节点B的数据项，然后将真正指向节点C的指针删除即可实现将节点B“删除”！！关键代码如下：
pCurrent-&m_pNext =
pNext-&m_pN
pCurrent-&m_nKey =
pNext-&m_nK
完整代码如下：
struct ListNode
&&& ListNode*
m_pN&&&&&&
//参数必须是指向指针的指针，因为要修改指针
//所以要考虑“参数本地拷贝”问题
void InitList(ListNode** pList)
*pList = (ListNode*)malloc(sizeof(ListNode));
(*pList)-&m_pNext = NULL;
//第一个参数不必是指向指针的指针，因为函数内只修改指针指向的数据
//所以不用担心“参数本地拷贝”问题
void InsertList(ListNode* pList, int data)
&&& ListNode*
pNewNode = (ListNode*)malloc(sizeof(ListNode));
pNewNode-&m_nKey =
pNewNode-&m_pNext =
pList-&m_pN
pList-&m_pNext = pNewN
//核心算法
void DeleteRandomNode(ListNode* pCurrent)
assert(pCurrent != NULL);
&&& ListNode*
pNext = pCurrent-&m_pN
&&& if(pNext
pCurrent-&m_pNext =
pNext-&m_pN
pCurrent-&m_nKey = pNext-&m_nK
&&&&&&&&&&&&&&&&&&
pNext = NULL;
//打印链表元素
void PrintListNormally(ListNode* pListHead)
&&& ListNode*
pTempNode = pListHead-&m_pN
while(pTempNode != NULL)
std::cout&&pTempNode-&m_nKey&&std::
pTempNode =
pTempNode-&m_pN&&&&&&&&&&&&
int main()
&&& ListNode*
pHead = NULL;
InitList(&pHead);
&&& for(int
i=9; i&=0; i--)
InsertList(pHead,i);&&&&&&&
PrintListNormally(pHead);
&&& ListNode*
pNext = pHead-&m_pNext-&m_pN
//删除第个元素
DeleteRandomNode(pNext);
PrintListNormally(pHead);
system("pause");
&&& return
=======================================================
扩展题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
int&&&&&&&
ListNode*& m_pN
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode*
pToBeDeleted);
分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。
在链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是O(n)
我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。
上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是O(n)。
那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1总情况下时间复杂度是O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n，仍然为O(1)。
基于前面的分析，我们不难写出下面的代码。
核心参考代码：
//核心算法
//pListHead是链表头指针，pCurrent是要删除的节点指针
void DeleteRandomNode(ListNode* pListHead, ListNode*
assert(pCurrent != NULL || pListHead != NULL);
if(pCurrent-&m_pNext != NULL) //要删除的节点不是最后一个节点
ListNode* pNext = pCurrent-&m_pN
pCurrent-&m_nKey = pNext-&m_nK
pCurrent-&m_pNext =
pNext-&m_pN
NULL;&&&&&&&&&&&&&&&&&&&
//要删除的节点是链表中最后一个节点
ListNode* pNode = pListH
while(pNode-&m_pNext != pCurrent) //得到要删除节点的前继节点
&&&&&&&&&&&
pNode-&m_pN&&&&&&&&&&&&&&&&&&&&
pNode-&m_pNext = NULL;
pCurrent = NULL;
完整的代码只需替换第一题的相应函数，并在main函数调用中做相应修改即可。
值得注意的是，为了让代码看起来简洁一些，上面的代码基于两个假设：（1）给定的结点的确在链表中；（2）给定的要删除的结点不是链表的头结点。不考虑第一个假设对代码的鲁棒性是有影响的。至于第二个假设，当整个列表只有一个结点时，代码会有问题。但这个假设不算很过分，因为在有些链表的实现中，会创建一个虚拟的链表头，并不是一个实际的链表结点。这样要删除的结点就不可能是链表的头结点了。当然，在面试中，我们可以把这些假设和面试官交流。这样，面试官还是会觉得我们考虑问题很周到的。
天蝎座的moonlight
博客等级：
博客积分：0
博客访问：1,031
关注人气：0
荣誉徽章：您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
单链表实验报告总结.doc 31页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：100 &&
单链表实验报告总结
你可能关注的文档：
··········
··········
单链表实验报告总结
单链表实验报告
线性表基本操作的编程实现
--线性表在链表存储下的主要操作实现
班级:T523-1
完成日期: 地点:5502
学时:2学时
一、需求分析
【实验目的】
通过本次实验，对课堂上线性表的知识进行巩固，进一步熟悉线性表的
链接存储及相应的基本操作；并熟练掌握VC++ 6.0操作平台，学会调试程序，以及编写电子实验报告
【实验要求】
编写线性表的基本操作，有构造线性表，线性表的遍历，插入，删除，
查找，求表长等基本功能，在此基础上能够加入DOS下的图形界面以及学会文件的操作等功能，为以后的学习打下基础。
【实验任务】
(1).线性表基本操作的编程实现，掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。
(2).用菜单管理，把线性表的顺序存储和链表存储的数据插入、删除运算
进行程序实现。建议实现键盘数据输入实现改实验的通用性。为了体现功能的正常性，至少要编制遍历数据的函数.
(3).注意事项:开发语言使用C++，尽量使用面向对象的思想和实现方法，可以改编成应用软件.
【实验类型】
验证型实验
二、概要设计
需要实现线性表的以下功能:
正在加载中，请稍后... 上传我的文档
 下载
 收藏
很高兴通过道客巴巴这个网络平台，认识更多的朋友。
 下载此文档
正在努力加载中...
单链表原地逆置(头插法)
下载积分：2000
内容提示：单链表原地逆置(头插法)
文档格式：DOCX|
浏览次数：11|
上传日期： 04:30:44|
文档星级：
全文阅读已结束，如果下载本文需要使用
 2000 积分
下载此文档
该用户还上传了这些文档
单链表原地逆置(头插法)
关注微信公众号posts - 353,&
comments - 50,&
trackbacks - 0
题目：有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand（可能为空，也有可能为自身），如何拷贝这个特殊链表？
拷贝pNext指针非常容易，所以题目的难点是如何拷贝pRand指针。假设原来链表为A1 -& A2 -&... -& An，新拷贝链表是B1 -& B2 -&...-& Bn。为了能够快速的找到pRand指向的节点，并把对应的关系拷贝到B中。我们可以将两个链表合并成A1 -& B1 -& A2 -& B2 -& ... -& An -& Bn。从A1节点出发，很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx，将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。依次类推。当所有节点的pRand都拷贝完成后，再将合并链表分成两个链表就可以了。
这个题目有个很巧妙的解法，可以达到O(n)的效率，其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表，然后给复制链表中每个节点的随机指针复制，最后再打断链表恢复原样。
代码如下：
typedef struct __Node
__Node* pN
__Node* pR
Node* DuplicateList(Node* pSrcListHead)
if (pSrcListHead == NULL)
return NULL;
Node* pNode = pSrcListH
while (pNode != NULL)
Node* pNewNode = new N
pNewNode-&nData = pNode-&nD
pNewNode-&pNext = pNode-&pN
//pNewNode-&pRandom = pNode-&pR
pNode-&pNext = pNewN
pNode = pNewNode-&pN
Node* pDestListHead = pSrcListHead-&pN
pNode = pSrcListH
while (pNode != NULL)
pNode-&pNext-&pRandom = pNode-&pRandom-&pN
pNode = pNode-&pNext-&pN
pNode = pSrcListH
Node* pNode2 = pNode-&pN
while (pNode != NULL)
pNode-&pNext = pNode2-&pN
pNode = pNode-&pN
if (pNode)
pNode2-&pNext = pNode-&pN
pNode2-&pNext = NULL;
pNode2 = pNode2-&pN
return pDestListH
不过，目前还未考虑到原始链表有环的情况，如果原始链表有环，则应该先求出环的入口点，然后利用上面的方法进行链表复制。
阅读(...) 评论()