ChunNote
0%

leetCode-237:Delete Node in a Linked List

发表于 分类于

问题描述

给定一个链表中的某个节点（非链表最后一个节点），要求删除这个节点（可以不必在内存中删除，只要求链表中没有这个值的节点即可）。题目链接：**点我**

样例输入输出

输入：head = [4,5,1,9], node = 1

输出：[4, 5, 9]

输入：head = [4,5,1,9], node = 5

输出：[4, 1, 9]

问题解法

此题跟常规的删除链表节点不一样，常规的是需要知道头节点，然后从链表中将这个节点剔除。但是本题并没有给头节点，同时并不要求这个节点从链表中实质删除这个节点，说明可以删除其他节点，只要链表的数量比原先少1，且顺序保持不变即可。所以，可以把后续的节点值往前移，删除最后一个节点。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        ListNode prev = node;
        while (node.next != null) {
            node.val = node.next.val;
            prev = node;
            node = node.next;
        }

        prev.next = null;
    }
}

优化一点的做法是，直接将下个节点的值赋给当前节点，然后删除下个节点，这样后续的节点都不用改变。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

参考资料

https://leetcode.cn/problems/delete-node-in-a-linked-list/solution/shan-chu-lian-biao-zhong-de-jie-dian-by-x656s/