【题目】
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9],它可以表示为:
示例 :
输入: head = [,,,], node =
输出: [,,]
解释: 给定你链表中值为 的第二个节点,那么在调用了你的函数之后,该链表应变为 -> -> 9.
示例 :
输入: head = [,,,], node =
输出: [,,]
解释: 给定你链表中值为 的第三个节点,那么在调用了你的函数之后,该链表应变为 -> -> 9.
说明:
链表至少包含两个节点。 链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。 不要从你的函数中返回任何结果。
【思路】
说个题外话,我在做题时,陷入思维局限了,想着删除链表节点一定要考虑两种情况:头结点、一般节点及尾节点。于是判断是否为头结点,是的话,改变头指针指向,删除原来的头结点;否则,找到删除的节点q及其前一个节点p,修改指针,p->next = q->next,最后删除q节点。
但是,本题函数只传入了一个指针!!该指针指向的是删除的节点。
好像很复杂?那怎么才能找到前一个节点?
不用!
修改节点的val值以及next指针即可。
【代码】
python版本
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
C++版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* p = node->next;
node->val = node->next->val;
node->next = node->next->next;
delete p;
}
};