题目信息
题目地址: https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 -- head = [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.
提示:
题解
作为合集中链表下的第一题,确实是较简单的只是一个单元操作,但如果不知道链表这种数据结构也还是是完成不了的。
链表是什么?
链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成,也就是包含值与模拟指针(引用)。大概如下:
每个节点对象除了内容值还有一个引用一共两个属性,这样以来各个节点对象之间就好像连接着一样
class ListNode{
//节点值
int val;
//节点指向的下个节点
ListNode next;
//构造器
ListNode(int x) {
val = x;
}
}
现在它传一条链表的一个节点,删除这个节点。因为一个节点的信息只有自己的值以及下个节点。所以传入一个节点是看不到整个链表的。也就是说我们只能拿到部分链就是传入的节点之后的5--->1--->9
。值为4的节点是指向5这个节点的,删除5节点就是让4节点直接指向1节点就可以了,但我们拿不到4节点所以不能改变它的next属性的值。那么我们只能改它指向的节点把它的值由5改成1再指向9
这样就不用改变4节点的指向,只是把它指向的这个对象值与next都改掉,那么4还是指向0x001只不过是1了,而这个指向的又是0x004就是9,链表也就变成了4--->1--->9完成删除5的操作
public void deleteNode(ListNode node) {
//“被删节点”的值改为下个节点的值
node.val = node.next.val;
//指向下下个
node.next = node.next.next;
}
总结
开篇第一题主要是考察学习链表构成,本身是简单的但先要了解这样一个数据结构。