删除链表的节点

第十八题，（第一个）题目如下： 思路如下：例如删除节点i；需要时间复杂度为O(1),则不能从头遍历，设节点i的下一个节点为节点j，则将节点j复制到节点i再将节点j删除，这就相当于把节点i删除了。 如果要删除的节点位于尾部，为最后一个节点则仍需从头开始遍历，得到该节点的前序节点，然后完成删除操作。 如果只有一个节点，删除后要把头结点置为空。 代码如下：

#include <stdio.h> #include <stdlib.h> struct ListNode { int m_nValue; ListNode* m_pNext; }; ListNode* create(int n) { ListNode* tail, * head, * q; head = tail = (ListNode*)malloc(sizeof(ListNode)); head->m_pNext = nullptr; for (int i = 0; i < n; i++) { q = (ListNode*)malloc(sizeof(ListNode)); scanf("%d", &q->m_nValue); q->m_pNext = nullptr; tail->m_pNext = q; tail = q; } return head->m_pNext; } void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted) { if (!pListHead || !pToBeDeleted) return; if (pToBeDeleted->m_pNext != nullptr) { ListNode* pListNode = pToBeDeleted->m_pNext; pToBeDeleted->m_nValue = pListNode->m_nValue; pToBeDeleted->m_pNext = pListNode->m_pNext; delete pListNode; pListNode = nullptr; } else if (*pListHead == pToBeDeleted) { delete pToBeDeleted; pToBeDeleted = nullptr; *pListHead = nullptr; } else { ListNode* pNode = *pListHead; while (pNode->m_pNext != pToBeDeleted) pNode = pNode->m_pNext; pNode->m_pNext = nullptr; delete pToBeDeleted; pToBeDeleted = nullptr; } } void Print(ListNode * head) { if (head == nullptr) return; while (head != nullptr) { printf("%d ", head->m_nValue); head = head->m_pNext; } } int main() { int n,num; printf("请输入要创建的链表的长度："); scanf("%d", &n); printf("请输入你要创建的链表："); ListNode* a = create(n); printf("你输入的链表为："); Print(a); printf("\n请输入要删除第几个节点："); scanf("%d",&num); ListNode* b = a; for (int i = 0; i < num&&b->m_pNext !=nullptr; i++) b = b->m_pNext; DeleteNode(&a, b); printf("删除第%d个节点后该链表为：",num); Print(a); printf("\n"); }

运行结果如下： 题目删除函数给的是指向指针的指针，故创建了一个没有头节点的链表。