1.思路

假设链表......---A--B--C--D....,要删除B。一般的做法是遍历链表并记录前驱节点,修改指针,时间为O(n)。删除节点的实质为更改后驱指针指向。这里,复制C的内容至B(此时B,C同时指向D),删除节点C,即达到间接删除节点B的目的。

倘若B是链尾节点。则需要线性遍历寻找前驱节点。

以上思路,时间复杂度为O(1)。

2.代码

struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}; void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
if(!*pListHead||!pListHead || !pToBeDeleted)
return; // 非链表尾指针
if(pToBeDeleted->m_pNext != NULL)
{
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nKey = pNext->m_nKey;
pToBeDeleted->m_pNext = pNext->m_pNext; delete pNext;
pNext = NULL;
}
else if(pListHead==pToBeDeleted){
delete *pListHead;
*pListHead=NULL;
pToBeDelete=NULL;
}
else
{
ListNode* pNode = *pListHead;
while(pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
} // deleted pToBeDeleted
pNode->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;//重要,释放所属空间后,指针置空
}
}

3.链表查找节点

1)查找倒数第k个节点:使用双指针,间距为k-1,当,后一个指针指向对尾的时,前一个指针所指即可所求;

2)奇数个节点链表查找中间节点:设置双指针,初始化指向头结点。一个每次跳两步,一个每次跳一步。当前一个指针指向队尾,后一个指针所指即为所求;

3)偶数个节点查找中间2个节点:设置双指针,初始化指向头结点。一个每次跳两步,一个每次跳一步。当前一个指针指向队尾,后一个指针所指和后驱节点即为所求;

4.判断单向链表是否为环形结构。定义两个指针,一个一次两步,一个一次一步,倘若两个指针最后能追上,则为环形结构。

参考:

1.每天一道算法题2 删除链表结点(时间复杂度为O(1)    2.每天一道算法题7 查找链表中倒数第k个结点

05-11 11:13
查看更多