问题:
给定一个单向链表,设计一个时间优化并且空间优化的算法,找出该链表的倒数第m个元素。实现您的算法,注意处理相关的出错情况。m定义为当m=0时,返回链表最后一个元素。
解答:
这是一个难题,因为单向链表只能正向遍历,这个问题需要根据元素与链表尾的相对位置来找出该元素,但是当发现链表尾时,没有简单的办法回溯到倒数第m个元素。
我们需要的是倒数第m个元素,所以,如果我们从某个元素开始,遍历了m个元素之后刚好到达链表末尾,那这个元素就是要找的元素。一种方法是简单的以这种方式检查每个元素,直到找到要找的元素为止。但这样同样的元素会被遍历多次,针对链表中大部分元素我们都会遍历m个元素,如果链表的长度是n的话,那么这个算法的时间复杂度就是O(mn)。
也许从链表的尾部倒推回去不是最好的办法,那么我们可以从链表头开始计数。
思路一:想要的元素是倒数第m个元素,而我们知道m值。它肯定是从链表头算起的第x个元素,且x+m=n,即链表的长度。而计算出链表的所有元素个数是容易的。之后就可以算出x=n-m,并从链表头开始遍历x个元素。尽管这个算法需要2次遍历链表,但它的时间复杂度仍是O(n)。同时,如果我们可以修改链表的函数,在添加元素时对一个计数遍历加1,在删除元素时对这个计数变量减1,我们就可以省掉链表长度计算的过程,使它更有效率。
上面思路的缺点是:如果这是一个很长的链表而计算机的内存又有限,那么这个链表的大部分很可能都存放在切换出物理内存的虚拟内存上(即存放在磁盘上)。如果真是这样,那么链表的每次遍历都将需要做大量的磁盘读写操作才能把链表的有关部分读到物理内存里来进行处理。在这种情况下,如果算法只需对链表做一次完整的遍历,那么它将比必须做两次遍历的算法快很多---虽然它们都是O(n)级的算法。
但是,如果不能修改链表的数据结构呢?在上面的分析中,当我们到达链表的末尾时,实际上只对保存下来的m个元素中的一个感兴趣,即当前位置的前面第m个元素。我们之所以记下m个元素只是因为当前位置的前面第m个元素在每次移动位置时都会改变。保持一个m个元素的队列,每次在移动当前位置时,将当前元素添加在头部,在尾部删除一个元素,这样做只是为了确保队列中最后一个元素总是当前位置的前面第m个元素。
思路二:透过想象看本质,上面我们使用这个m个元素的数据结构来隐式地移动一个前m个元素的指针,保持它与当前位置的指针同步移动。但是,这个数据结构是不必要的,我们可以显式地移动前面第m个元素的指针,就像移动当前位置的指针一样,这与通过一个队列隐式地移动同样简单,这样一来,就无需保存当前位置和前面第m个元素之间的所有元素。这个算法的优点是:线性时间复杂度、一次遍历、可以忽略的存储要求。
此时,我们需要使用两个指针:一个当前位置指针和一个前面第m个元素的指针。需要确保两个指针之间相差m个元素,然后以同样的速度移动它们。如果当前指针到达链表的末尾,前面第m个元素的指针就是指向倒数第m个元素。同时要注意边界条件,如果链表的长度小于m,那么就没有倒数第m个元素,因此,在移动当前指针时要检查是否到达链表的末尾。
实现代码如下:
#include <iostream>
#include <assert.h>
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
void InitList(ListNode** pList)
{
*pList = (ListNode*)malloc(sizeof(ListNode));
(*pList)->m_pNext = NULL;
}
void InsertList(ListNode* pList, int data)
{
assert(pList != NULL);
ListNode* pNewNode = (ListNode*)malloc(sizeof(ListNode));
pNewNode->m_nKey = data;
pNewNode->m_pNext = pList->m_pNext;
pList->m_pNext = pNewNode;
}
//思路一的核心算法
//注意:链表最后一个元素是倒数第0个
ListNode* findMLastElement1(ListNode* head, unsigned int m)
{
if(head == NULL)
return NULL;
//计算链表中节点数º
ListNode* pCurrent = head->m_pNext;
unsigned int nCount = 0;
while(pCurrent != NULL)
{
pCurrent = pCurrent->m_pNext;
nCount++;
}
//如果链表中节点数少于m,返回NULL
if(nCount < m)
return NULL;
//链表倒数第m个节点就是从链表开头第nCount-m个节点
//注意:m从0开始
pCurrent = head;
for(unsigned int i=0; i<nCount-m; i++)
{
pCurrent = pCurrent->m_pNext;
}
return pCurrent;
}
//思路二的核心算法
//注意:链表最后一个元素是倒数第个
ListNode* findMLastElement2(ListNode* head, unsigned int m)
{
if(head == NULL)
return NULL;
ListNode *current, *mBehind;
current = head;
for(int i=0; i<m; i++)
{
//current设置为当前指针,它前面必须存在第m个元素,否则出错
if(current->m_pNext != NULL)
{
current = current->m_pNext;
}
else
{
return NULL;
}
}
mBehind = head; //当前位置current的前面第m个元素的指针,从链表头开始移动
while(current->m_pNext != NULL)
{
current = current->m_pNext;
mBehind = mBehind->m_pNext;
}
return mBehind;
}
//打印链表元素
void PrintListNormally(ListNode* pListHead)
{
ListNode* pTempNode = pListHead->m_pNext;
while(pTempNode != NULL)
{
std::cout<<pTempNode->m_nKey<<std::endl;
pTempNode = pTempNode->m_pNext;
}
}
int main()
{
ListNode* pListHead = NULL;
InitList(&pListHead);
for(int i=9; i>=0; i--)
{
InsertList(pListHead, i);
}
PrintListNormally(pListHead);
ListNode* findNode = NULL;
findNode = findMLastElement1(pListHead, 3);
std::cout<<"链表中倒数第3个元素是:"<<findNode->m_nKey<<std::endl;
findNode = findMLastElement2(pListHead, 4);
std::cout<<"链表中倒数第4个元素是:"<<findNode->m_nKey<<std::endl;
system("pause");
return 0;
}
扩展问题:
如何获得处于单链中间位置的节点(只能遍历链表一次!)
解答:
其实原理和上面的一样,就是设置两个指针,或游标(形象点):
Element *pSlow = head;//标识当前节点
Element *pFast = head;//标识当前节点的下一个节点
将慢游标前进步长设为1,快游标前进步长设为2:
pSlow = pSlow->next;//前进一个节点
pFast = pFast->next->next;//前进两个节点因此,快游标是慢游标速度的两倍,
//当快游标到达链表尾节点或尾节点前一个节点时,慢游标正好处于链表的
//中间位置,即为所求。
分享到:
相关推荐
删除链表中倒数第N个结点后,返回结果链表的首结点
只遍历一次单向链表,找到倒数第N个结点,
取单链表倒数第k个元素,包括算法描述、算法思想,算法实现等
NULL 博文链接:https://128kj.iteye.com/blog/1748487
链表中倒数第k个节点.md
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级...
删除链表的倒数第 N 个结点.md
编写一个数组,利用链式 不是顺序的 实现元素 排序 查找 插入等!
删除链表的倒数第N个节点、面试题02.07.链表相交和142.环形链表II。记录了清晰的文字题解+图示以及Java参考代码。 适合人群:链表算法感兴趣的程序员或学生,想要打好数据结构与算法基础的人。 能学到什么:掌握链表...
判断链表是否为回文链表 leetcode leetcode-javascript LeetCode 算法练习题解 数据结构与算法 旋转矩阵 零矩阵(编写一种算法,若 ...删除链表的倒数第 N 个节点 反转链表 移除链表元素 奇偶链表 回文链表 排序 sort
本文实例讲述了python实现获取单向链表倒数第k个结点的值。分享给大家供大家参考,具体如下: #初始化链表的结点 class Node(): def __init__(self,item): self.item = item self.next = None #传入头结点,获取...
面试题目1:获取倒数第N个节点 面试题目2:获取倒数第N个节点 面试题3:逆序打印(这里使用栈的方式) 链表(Linked List)介绍【单链表篇】 链表包括:1.单链链表 ; 2.双链链表 ; 3. 环状链表 链表是有序的列表,...
本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点。 代码: class LinkedListAlgorithms(object): def __init__...
删除链表的倒数第N个节点 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n ...
删除单链表和双链表倒数第K个节点 删除链表的中间节点和a/b处的节点 腕单向链表和链 部分单向链表 环形单链表的约瑟夫问题 一个鉴定链表是否为回文结构 将单向链某值分割成小表、送、按右边大的形式 复制带有日常...
找到链表中倒数第k个节点 不同实现 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 (-k+1+链表总数) % 链表总数 查询链表的中间节点 一个每次...
/* *实现算法查找单链表中的倒数第N个元素 *
代码中包含单链表的常用操作,主要实现以下六个算法: 1.单链表的就地反转 2.链表相交或求公共起始节点...3.求链表倒数第n个节点 4.删除单个节点 5.判断链表是否有环 6.将2个递增的链表合并为递减链表 并全部调试通过。
(即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。) 四、思考与提高 1.如果上面实验内容2中合并的表内不允许有重复的数据该如何操作? 2.如何将一个带头结点的单链表La分解成两个...