【编程题目】在 O(1)时间内删除链表结点

时间:2024-01-04 20:28:38

60.在 O(1)时间内删除链表结点(链表、算法)。
题目:给定链表的头指针和一个结点指针,在 O(1)时间删除该结点。链表结点的定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下:
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

思路:把当前结点的下一个结点的内容复制到当前结点,删除下一结点即可。 注意,链表中只有一个结点时在题目给定的函数声明下无法删除,删除最后一个结点时需要从头寻找。

/*
60.在 O(1)时间内删除链表结点(链表、算法)。
题目:给定链表的头指针和一个结点指针,在 O(1)时间删除该结点。链表结点的定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下:
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
*/
#include <stdio.h>
#include <stdlib.h> typedef struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}ListNode; void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted)
{
if (pToBeDeleted == NULL || pListHead == NULL)
{
return;
}
if (pToBeDeleted->m_pNext == NULL) //删除最后一个节点
{
ListNode* x = pListHead;
if (pToBeDeleted == pListHead) //只有一个节点
{
printf("can't delete the only note\n");
}
else
{
while (x->m_pNext != pToBeDeleted) //删除最后一个节点必须循环删 直接赋值NULL是不行的 因为输入的是指针的一个副本
{
x = x->m_pNext;
}
x->m_pNext = NULL;
free(pToBeDeleted);
}
return;
}
//把下一个结点的数据复制到当前结点,实际删除下一结点
ListNode * tmp = pToBeDeleted->m_pNext;
pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey;
pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
free(tmp);
} void printList(ListNode* pListHead)
{
ListNode* x = pListHead;
while (x != NULL)
{
printf("%d ->" , x->m_nKey);
x = x->m_pNext;
}
printf("\n");
} void createList(ListNode* &pListHead)
{
int data;
scanf("%d", &data);
if (data != )
{
pListHead = (ListNode*)malloc(sizeof(ListNode));
pListHead->m_nKey = data;
pListHead->m_pNext = NULL;
createList(pListHead->m_pNext);
}
} int main()
{
ListNode * p = NULL;
createList(p);
printList(p);
DeleteNode(p, p->m_pNext);
printList(p); return ;
}