刷Leetcode刷到一个很有意思的题目，解题思路很新颖，题目如下：

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list – head = [4,5,1,9], which looks like following:

1
4 -> 5 -> 1 -> 9

Definition for singly-linked list.

1
2
3
4
5
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
  • The linked list will have at least two elements.
  • All of the nodes’ values will be unique.
  • The given node will not be the tail and it will always be a valid node of the linked list.
  • Do not return anything from your function.

题目大意是，给定一个要删除的节点，要求在这个节点所在的链表中删除该节点

假设要删除的节点是 a ，常规做法是从链表头开始遍历找到 a 的前一个节点，假设为 b，将 b 的 next 指针指向 a 的 next就可以了。但是题目只给定了待删除的节点，没有给链表的头结点，似乎束手无策了。

其实稍加思索可以发现，我们要删除的不是节点本身，而是节点的内容，以此题为例，节点里面的内容只有两个东西，val和next指针。如果我们要删除该节点，只需要把b的后一个节点的内容复制到b节点，然后跳过b节点的下一个节点即可。如图

删除节点 b
删除节点 b

实现代码也比较简单

1
2
3
4
public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

解题思路确实很新颖，之前没有想过可以这么做，其实这题完全可以出的更具迷惑性，把链表首结点也给出，大多数人可能都会遍历整个链表来删除节点。

多刷题果然是有好处的。