假设现有一个单向的链表,但是只知道只
有一个指向该节点的指针p,并且假设这个节点不
是尾节点,试编程实现删除此节点
写一算法检测单向链表中是否存在环
(whether there is a loop in a link list),
要求算法复杂度(Algorithm's complexity 是
O(n)) 并只使用常数空间(space is O(c)).
注意,你只知道一个指向单向链表头的指针。
链表的长度是不定的,而且环出现的地方也是不定
的,环有可能在头,有可能在中间。而且要求是检
测, 不能破坏环的结构.
(1)编写一个算法,从任一给定的位置(pr,p)开始,将指针p右移k个结点。如果p移出链表,则将p为0,并让pr停留在链表最右边的结点上。
(2)编写一个算法,从任一给定的位置(pr,p)开始,将指针p左移k个结点。如果p移出链表,则将p置为0,并让pr停留在链表最左边的结点上。
面试题:在O(1)时间删除链表结点
题目:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除链表结点。链表结点与函数的定义如下:
struct List Node
{
int m_n Value;
ListNode* m_pNext;
};
void DeleteNode (listNode** plistHead, ListNode* pToBeDeleted);