LeetCode面试题之删除单链表节点
1.限制于要求
只给要删除的数据节点的指针,指针不会指向链表尾。
2.思考
正常删除一个链表中的节点我们先要获取要删除节点的前驱节点的指针pre,然后执行pre->next = pre->next->next来把要删除的节点从链表中剔除。其实这里我们可以转换一下思维方式不一定要通过删除节点的方式来删除数据,我们可以通过复制要删除节点的下一个节点的数据到当前要删除的节点中,然后再把要删除节点的下一个节点给删除,就能达到删除指定节点上数据的要求。
3.算法图解
- 获取要删除节点的下一个节点
- 复制下一个节点值到当前节点中,删除下一个节点
4.代码实现
/* 83 / 83 test cases passed. Status: Accepted Runtime: 16 ms CreateTime: 2016年5月28日 01:37:59 Desc: 要打破固有思维,删除节点不一定要删除指定的节点,这里的一个变通就是删除下一个节点,在删除下一个节点之前 把下一个节点的值设置到上一个要删除的节点中,效果就跟上一个节点被删除一样。 */ struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: void deleteNode(ListNode* node) { ListNode * dnode = node; node = node->next; dnode->val = node->val dnode->next = node->next; //因为node不是最后一个节点,故这里node必定非NULL。 } };
5.OJ练习
LeetCode:https://leetcode.com/problems/delete-node-in-a-linked-list/
近期评论