leetcode.png
今天是一道简单的题目，注意认真审题噢。
题目
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
4 -> 5 -> 1 -> 9
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
链表定义
struct ListNode {
int val;
struct ListNode *next;
};
函数声明
void deleteNode(struct ListNode* node);
思路
最开始是准备以带头节点的方式, 然后以node.next = node.next.next 的方式删除节点, 但是仔细审题会发现函数声明的参数中只有一个. 这说明是一个不带头节点的链表.
有了这个前提, 算法的思路变成了两步
- 查找这个结点.
- 删除这个结点.
问题
根据上面的思路, 如果我们用以往的改变结点 next 指向的方式的话, 并不太可行. 原因是链表没有前指针, 指针指向的是当前的结点. 另外, 就算把条件设置为 while(node.next.val != node.val) 也是不可取的, 因为这时结点在首位的情况会被忽略.
于是我们换个方式, 直接把当前结点用下一个结点替换掉, 这是基于题目中给的 给定的节点为非末尾节点 这一条件作出的解法.
实现
第一版
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
while node is not node:
node = node.next
node.val = node.next.val
node.next = node.next.next
结果
C实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void deleteNode(struct ListNode* node) {
while (node->val != node->val)
node = node->next;
node->val = node->next->val;
node->next = node->next->next;
}
结果
第二版
第一版的结果在Python下表现一般, 于是我观摩了一下评论区的大佬, 发现查找部分可以直接省略.
这是为啥?
原因是函数传入的值不是一个数值, 而是一个结点. 已知一个结点, 它的下一个所指也就确定了, 因此直接把结点删除不需要查找了. 最终的答案如下.
Python实现
class Solution:
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实现
void deleteNode(struct ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
