237. Delete Node in a Linked List（leetcode）

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

写一个函数来删除单链表中的一个节点（除了尾部），只允许访问那个节点。
假设链表是1 - > 2 - > 3 - > 4，你得到了第三个值为3的节点，在调用你的函数后，链表应该变成1 - >2 -> 4。

节点代码：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

思路：容易想到，传入一个node，在只允许访问node 的情况下，可以知道的值有: node.val, node.next，node.next.val，node.next.next.....（若非空）

假设有一个链表如图所示：node 是节点2，它前面有节点1，后面有节点3。结合题意，如下步骤进行删除：

如果删除掉或者用节点3代替node（节点2），那么节点1将会丢失，因为并不能改掉1.next的指向，因此要保留node节点和它的前驱节点。
在保留节点node的情况下，只需把node.next节点（即节点3）的值去替换节点node的值，那么这个node将会变成节点3，即伪删除了（并没有真正从内存空间删除node，只是替换值而已）（蓝色线条）
再把最后一个节点（节点4）替换节点3，即node.next=node.next.next，真正从内存空间删除了node.next（即节点3被删除了，节点4替代了节点3）（棕色线条）
最后，得到一个删除了node的节点的链表（然而实际删除的是node.next，node只是值替换了而已）

代码如下：

public class Solution {

    public void deleteNode(ListNode node) {

        node.val = node.next.val;

        node.next = node.next.next;

    }

}

巴特西

237. Delete Node in a Linked List（leetcode）

最新文章

热门文章