【算法训练-链表 四】【链表删除】:删除链表的倒数第N个节点、删除有序链表中的重复元素、删除有序链表中的重复元素II

简介: 【算法训练-链表 四】【链表删除】:删除链表的倒数第N个节点、删除有序链表中的重复元素、删除有序链表中的重复元素II

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【删除有序链表中的重复元素】,使用【链表】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。

名曲目标题后,附上题目链接,后期可以依据解题思路反复快速练习,题目按照题干的基本数据结构分类,且每个分类的第一篇必定是对基础数据结构的介绍

删除链表的倒数第N个节点【MID】

来解决这道MID题目

题干

输入:
{1,2},2    
返回值:
{2}

解题思路

给出解题思路

算法实现步骤如下:

  1. fast快指针先行N步和慢指针拉开N个节点距离
  2. fast和slow指针一直向前直到快指针到链表的尾节点停止,此时慢指针因为落后快指针N个节点,所以在链表的倒数第N+1个位置
  3. slow指针直接指向其下一个节点的下一个,将下一个节点从链表中删除

注意这里为什么用了虚拟头结点作为哨兵,如果要删除的是倒数第5个节点也就是头节点,按照上述算法将无法处理,所以需要设置一个虚拟头节点

代码实现

给出代码实现基本档案

基本数据结构链表

辅助数据结构

算法迭代

技巧双指针

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 1 入参校验及哨兵节点设置
        if (head == null) {
            return null;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // 2 定义快慢指针,都从表头出发
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        // 3 快指针先行N步,拉开与慢指针N个节点间隔
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        // 4 快慢指针同时前进,当快指针到链表尾部的时候,慢指针就对应倒数第N个节点的前一个节点,因为快慢指针拉开的是N个节点距离
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}

复杂度分析

时间复杂度:由于只遍历了一遍,所以时间复杂度为O(N)

空间复杂度:由于没有用到辅助空间,所以空间复杂度为O(1)

删除有序链表中的重复元素【EASY】

先来个简单的热热身

题干

解题思路

比较简单,由于链表有序,则重复元素一定相邻,删除重复元素即可。

代码实现

给出代码实现基本档案

基本数据结构链表

辅助数据结构

算法迭代

技巧

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 1-单指针进行链表遍历
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            // 2-只有当前节点和下一节点都不为null才能进行val比较
            if (cur.val == cur.next.val) {
                // 2-1 比较一致则删除下一个节点
                cur.next = cur.next.next;
            } else {
                // 2-2 比较不一致则继续向前搜索,直到cur到链表尾部
                cur = cur.next;
            }
        }
        return head;
    }
}

复杂度分析

时空复杂度分析

  • 时间复杂度:遍历一遍链表,所以时间复杂度O(N)
  • 空间复杂度:未用到辅助结构,所以空间复杂度O(1)

删除有序链表中的重复元素II【MID】

难度升级,和上一题的区别是把重复的元素全部干掉而不是留一个,所以需要有pre指针记录重复节点的上一个

题干

解题思路

这里需要注意虽有有两个while,但是内层的while是去重用的,它前进的时候也会影响到外层循环,所以总体时间复杂度就不是O(N^2),而是O(N)

代码实现

给出代码实现基本档案

基本数据结构链表

辅助数据结构

算法迭代

技巧双指针

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 1 入参校验
        if (head == null || head.next == null) {
            return head;
        }
        // 2 设置哨兵节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        // 3 双指针遍历
        while (cur != null && cur.next != null) {
            if (cur.val != cur.next.val) {
                // 1-比较不一致则继续前进
                cur = cur.next;
                pre = pre.next;
            } else {
                // 2-比较一致则cur继续向前直到直到不一致的为止
                while ( cur != null && cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // 3-删除中间所有的重复节点,cur继续指向新节点
                pre.next = cur.next;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

复杂度分析

时空复杂度分析

  • 时间复杂度:这里需要注意虽有有两个while,但是内层的while是去重用的,它前进的时候也会影响到外层循环,所以总体时间复杂度就不是O(N^2),而是O(N)
  • 空间复杂度:没有借助外部结构,空间复杂度为O(1)
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
39 1
|
2月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
52 0
Leetcode第21题(合并两个有序链表)
|
2月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
79 1
|
2月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
109 0
|
2月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
47 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
100 10
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
56 0
|
2月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
18 0
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
33 0

热门文章

最新文章