1. 首页
  2. 文章中心
  3. Coding

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

69 阅读 0 评论
我是靠谱客的博主 会撒娇八宝粥，最近开发中收集的这篇文章主要介绍【剑指Offer】个人学习笔记_18_删除链表的节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目录

    • 题目：
        • [剑指 Offer 18. 删除链表的节点](https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/)
        • 题目分析
    • 初始解答：
      • 方法一:
      • 方法二：
      • 方法三：
    • 从头到尾打印链表
    • 总结

刷题日期：20:4237 星期四2021年3月25日

个人刷题记录，代码收集，来源皆为leetcode

经过多方讨论和请教，现在打算往Java方向发力

主要答题语言为Java

题目：

剑指 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_删除链表的节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(46)

相关文章

0010【数组】简单LeetCode283.移动零
0010【数组】简单LeetCode283.移动零
java 静态类 空指针_Java 空引用访问静态不会发生空指针异常
java 静态类 空指针_Java 空引用访问静态不会发生空指针异常
redisTemplate 报空指针异常
redisTemplate 报空指针异常
关于hibernate的一对多ORM映射关系中一方Set<E>中空指针异常解决方案
关于hibernate的一对多ORM映射关系中一方Set中空指针异常解决方案
【剑指Offer】个人学习笔记_18_删除链表的节点
【剑指Offer】个人学习笔记_18_删除链表的节点
移动零的四种实现方式（逐步优化）
移动零的四种实现方式（逐步优化）
[LeetCode] Longest Palindrome Substring 详细分析
[LeetCode] Longest Palindrome Substring 详细分析
set方法在set传入值时报空指针异常，直接设置定值即可
set方法在set传入值时报空指针异常，直接设置定值即可

评论列表共有 0 条评论

立即
投稿
返回
顶部