删除链表中的节点

题目地址：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.

提示：

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

题解

作为合集中链表下的第一题，确实是较简单的只是一个单元操作，但如果不知道链表这种数据结构也还是是完成不了的。

链表是什么？

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成，也就是包含值与模拟指针（引用）。大概如下：

每个节点对象除了内容值还有一个引用一共两个属性，这样以来各个节点对象之间就好像连接着一样

1
2
3
4
5
6
7
8
9
10
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的操作

1
2
3
4
5
6
public void deleteNode(ListNode node) {
    //“被删节点”的值改为下个节点的值
    node.val = node.next.val;
    //指向下下个
    node.next = node.next.next;
}

总结

开篇第一题主要是考察学习链表构成，本身是简单的但先要了解这样一个数据结构。