【剑指Offer】个人学习笔记_18_删除链表的节点

题目：

剑指 Offer 18. 删除链表的节点

难度简单110

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意：**此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

题目分析

链表题目，链表定义在代码中也已经给出。

要实现功能，肯定先得对链表进行查找，如果与所求值相等，则标记找到节点，同时存储前一个结点的指针，指向该节点的指针所指，即删除了这个节点，然后返回链表头即可。

初始解答：

代码写法参考了部分资料，首先自己尝试实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        //首先得在链表中找到该节点
        ListNode node = head; //Java中链表的定义方法
        int cut = 0; //记录要删除节点的位置，先用笨办法
        while (node.val != val) { //只要找不到节点就一直往后找，找到则停
            node = node.next; //停下来的话，node.val == val
            cut ++;
        }
        //如何记录前一个节点
        ListNode pre = head; //Java中链表的定义方法
        int j = 0; //记录要删除节点的位置，先用笨办法
        while (j < cut -1) { //前进到要删除节点的前面
            pre = pre.next; //停下来的话，node.val == val
            j ++;
        }
        //此时pre指向要删除的前面，node即为要删除的节点
        pre.next = node.next;
        return head;
    }
}

能够跑的过示例，但是在

执行结果：解答错误

显示详情

输入：

[-3,5,-99] -3

输出：

[-3,5,-99]

预期结果：

[5,-99]

处错误了，可以发现这里要删除的是头节点，增加考虑后，又凭着自己的思考做出来题了，越来越能从中获得快乐了，继续加油。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        //首先得在链表中找到该节点
        ListNode node = head; //Java中链表的定义方法
        int cut = 0; //记录要删除节点的位置，先用笨办法
        while (node.val != val) { //只要找不到节点就一直往后找，找到则停
            node = node.next; //停下来的话，node.val == val
            cut ++;
        }
        //如何记录前一个节点
        ListNode pre = head; //Java中链表的定义方法
        int j = 0; //记录要删除节点的位置，先用笨办法
        while (j < cut -1) { //前进到要删除节点的前面
            pre = pre.next; //停下来的话，node.val == val
            j ++;
        }
        if (head.val == val) return head.next; //考虑头节点的情况
        //此时pre指向要删除的前面，node即为要删除的节点
        pre.next = node.next;
        return head;
    }
}

慢慢走 2020-02-29

原题的意思是在o(1)时间内删除一个确定在链表中的节点，leetcode又把原著的简单化了。

看了一圈，大家的方法都差不多。学习方法三官方精选的更简练的代码方式：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head.val == val) return head.next; //考虑头节点的情况
        //首先得在链表中找到该节点
        ListNode pre = head, cur = head.next; //Java中链表的定义方法
        while (cur != null && cur.val != val) { //只要找不到节点就一直往后找，找到则停
            pre = cur; //永远指向cur的前一个
            cur = cur.next; //停下来的话，cur.val == val
        }
        if (cur != null) pre.next = cur.next;
        return head;
    }
}

估计是概率问题，跑出来的空间效率还没我自己写的高，分布方式值得学习。

执行结果：通过

显示详情

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：37.9 MB, 在所有 Java 提交中击败了55.86%的用户

方法一:

弱鸡 2021-03-10

想了三种方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {


    public ListNode delNode(ListNode head, int val) {
        // 双节点
        ListNode pre = null, cur = head;
        while(cur.val != val)
        {
            pre = cur;
            cur = cur.next;
        }
        if(cur == head)
            head = head.next;
        else
            pre.next = cur.next;
        return head;
    }
    public ListNode delNode2(ListNode head, int val) {
        // 递归方案
        if(head == null)
            return null;
        if(head.val == val) return head.next;
        head.next = deleteNode(head.next, val);
        return head;
    }
    public ListNode delNode(ListNode head, int val) {
        // 在头结点添加一个节点
        ListNode fake = new ListNode(-1);
        fake.next = head;
        ListNode cur = fake;
        while(cur.next != null)
        {
            if(cur.next.val == val) 
                cur.next = cur.next.next;
            else
                cur = cur.next;
        }
        return fake.next;
    }
}

方法二：

小救星小渡（编辑过）20 分钟前

递归解法简单易懂

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode pre = null ;
        if(head == null){
            return head ;
        }
        else if(head.next == null && head.val == val){
            return pre ;
        }
        else if(head.next != null && head.val == val){
            head = head.next ;
        }
        pre = head ;
        head.next = deleteNode(head.next ,val);
        return head ;
    }
}

方法三：

官方精选解法，写法更精炼了，思想类似。

复杂度分析：

时间复杂度 O(N)O(N) ： NN 为链表长度，删除操作平均需循环 N/2N/2 次，最差 NN 次。

空间复杂度 O(1)O(1) ： cur, pre 占用常数大小额外空间。

作者：jyd

链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-shan-chu-lian-biao-de-jie-dian-sh-2/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：jyd

链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-shan-chu-lian-biao-de-jie-dian-sh-2/

来源：力扣（LeetCode）

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val) return head.next;
        ListNode pre = head, cur = head.next;
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if(cur != null) pre.next = cur.next;
        return head;
    }
}

从头到尾打印链表

这道题对链表的操作参考了第六题其他人用Java操作链表的代码，不然自己还在那里傻傻用->呢。

yuantjL1 （编辑过）2020-02-17

如果题目要求打印链表而不是返回数组，该如何解决？

不用栈，不用递归，双100%。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public static int[] reversePrint(ListNode head) {
        ListNode node = head;
        int count = 0;
        while (node != null) {
            ++count;
            node = node.next;
        }
        int[] nums = new int[count];
        node = head;
        for (int i = count - 1; i >= 0; --i) {
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
}

总结

以上就是本题的内容和学习过程了，大家的思路都差不多，学习更简单的写法。

欢迎讨论，共同进步。

【剑指Offer】个人学习笔记_18_删除链表的节点

目录

题目：

剑指 Offer 18. 删除链表的节点

题目分析

初始解答：

方法一:

方法二：

方法三：

从头到尾打印链表

总结

继续阅读

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程序设计

leetcode809

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

Linux设备模型（中）之上层容器

scala (3) Function 和 Method