当前位置： 首页 > article >正文

面试经典150题——链表（二）

article 2025/1/8 16:47:40

文章目录

  • 1、删除链表的倒数第 N 个结点
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 解题代码
    • 1.4 解题思路
  • 2、删除排序链表中的重复元素 II
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 解题代码
    • 2.4 解题思路
  • 3、旋转链表
    • 3.1 题目链接
    • 3.2 题目描述
    • 3.3 解题代码
    • 3.4 解题思路
  • 4、分隔链表
    • 4.1 题目链接
    • 4.2 题目描述
    • 4.3 解题代码
    • 4.4 解题思路
  • 5、LRU 缓存
    • 5.1 题目链接
    • 5.2 题目描述
    • 5.3 解题代码
    • 5.4 解题思路

1、删除链表的倒数第 N 个结点

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

1.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        int num = 0;
        while(cur.next != null){
            num++;
            cur = cur.next;
        }
        int deleteNum = num - n + 1; // 倒数第 n 个就是 整数第 num - n + 1个 
        cur = dummyHead;
        for(int i = 0; i < deleteNum - 1; ++i){
            cur = cur.next;
        }
        cur.next = cur.next.next;
    return dummyHead.next;
    }
}

1.4 解题思路

  1. 首先获取链表的总结点数num。
  2. 那么删除的结点就是正数第num - n + 1个结点。
  3. 按照链表的删除方式删除即可。

2、删除排序链表中的重复元素 II

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

2.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next != null){
            ListNode nextNode = cur.next;
            int flag = 0;
            while(nextNode.next != null && nextNode.next.val == nextNode.val){
                flag = 1;
                nextNode = nextNode.next;
            }
            if(flag == 0){
                cur = cur.next;
            } else{
                cur.next = nextNode.next;
            }
        }
        return dummyHead.next;
    }
}

2.4 解题思路

  1. 分情况讨论，cur指针指向判断结点的前1个结点，如果下一个结点存在相同的数字，则跳过这些数字，将cur.next与这些数字后面的一个数字所在的结点连接。否则的话，则需要保留这个结点，cur = cur.next。
  2. 当cur.next为空的时候不需要判断下个数字了，跳出循环即可。

3、旋转链表

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

3.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        int n = 0; // 链表中结点的个数
        while(cur.next != null){
            n++;
            cur = cur.next;
        }
        ListNode tail = cur;
        int step = k % n;
        if(step == 0){
            return head;
        }
        cur = dummyHead;
        for(int i = 0; i < n - step; ++i){
            cur = cur.next;
        }
        ListNode newHead = cur.next;
        tail.next = head;
        cur.next = null;
        return newHead;
    }
}

3.4 解题思路

  1. 解题思路看上去是统一右移动k位，实际上是将链表在第n - k位和 n - k + 1截断然后重新拼接。
  2. 第一段链表放在第二段链表的尾部即可。

4、分隔链表

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

提示：

  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

4.3 解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(); // 存储所有小于x的结点
        ListNode dummyHead2 = new ListNode(); // 存储所有大于等于x的结点 
        ListNode cur1 = dummyHead1;
        ListNode cur2 = dummyHead2;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                cur1.next = cur;
                cur1 = cur1.next;
                cur = cur.next;
                cur1.next = null;
            } else{
                cur2.next = cur;
                cur2 = cur2.next;
                cur = cur.next;
                cur2.next = null;
            }
        }
        cur1.next = dummyHead2.next;
        cur2.next = null;
        return dummyHead1.next;
    }
}

4.4 解题思路

  1. 用两个链表进行维护即可，一个链表用来存储值小于x的所有的结点，另一个链表存储大于等于x的所有的结点。
  2. 最后将两个链表拼接即可。

5、LRU 缓存

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

5.3 解题代码

public class DListNode{
    int key;
    int val;

    DListNode prev;
    DListNode next;

    DListNode(){}
    DListNode(int key, int val){this.key = key; this.val = val;}
    DListNode(int key, int val, DListNode prev, DListNode next){
        this.key = key;
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
} 


class LRUCache {
    Map<Integer, DListNode> hash = new HashMap<Integer, DListNode>(); 
    int size;
    int capacity;
    DListNode dummyHead = new DListNode();
    DListNode dummyTail = new DListNode();

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key) {
        if(hash.containsKey(key)){
            hash.get(key).prev.next = hash.get(key).next;
            hash.get(key).next.prev = hash.get(key).prev;
            moveToHead(hash.get(key));
            return hash.get(key).val; 
        }
        return -1;
    }
    
    public void put(int key, int value) {
        DListNode node = new DListNode(key, value);
        if(hash.containsKey(key)){
            hash.get(key).val = value;
            hash.get(key).prev.next = hash.get(key).next;
            hash.get(key).next.prev = hash.get(key).prev;
            moveToHead(hash.get(key));
        } else{
            if(size < capacity){
                ++size;
                moveToHead(node);
            } else{
                moveToHead(node);
                deleteTail();
            }
            hash.put(key, node);
        }
    }

    public void moveToHead(DListNode node){
        node.next = dummyHead.next;
        dummyHead.next = node;
        node.prev = dummyHead;
        node.next.prev = node;
    }

    public void deleteTail(){
        int key = dummyTail.prev.key;
        hash.remove(key);
        dummyTail.prev = dummyTail.prev.prev;
        dummyTail.prev.next = dummyTail;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

5.4 解题思路

  1. 使用双向链表解决问题。
  2. 对使用过的/新的值插入到链表开头。
  3. 删除链表末尾的结点。

http://www.kler.cn/a/470128.html

相关文章：

  • 虚表 —— 隐藏行（简单版）
  • 测试岗位的基础知识
  • tcpdump-命令详解
  • ollama安装及本地部署开源大模型
  • Mybatis（day09）
  • github开源链游详细搭建文档
  • ASP.NET Core 中服务生命周期详解：Scoped、Transient 和 Singleton 的业务场景分析
  • 汉诺塔..
  • React：构建现代 Web 应用的利器
  • 基于Node.js的水产品销售平台
  • linux 查看 MySQL 在 Linux 或 WSL 上的运行状态
  • WebSocket 测试调试：工具与实践
  • 哺乳动物各器官和物种中长链非编码RNA的发育动态
  • JMeter + Grafana +InfluxDB性能监控 （二）
  • 『SQLite』索引
  • 用MATLAB实现d2d通信中的模式选择
  • JS中函数基础知识之查漏补缺(写给小白的学习笔记)
  • Python AI教程之十一：监督学习之决策树（2）使用 sklearn 进行决策树回归
  • 6miu盘搜的使用方法
  • 如何利用Java爬虫批量获取商品信息
  • [python SQLAlchemy数据库操作入门]-23.SQLAlchemy 与 Redis 结合：缓存热门股票数据
  • 十种基础排序算法(C语言实现，带源码)(有具体排序例子，适合学习理解)
  • 动手学深度学习-深度学习计算-6GPU
  • 记一次k8s下容器启动失败，容器无日志问题排查
  • 日志记录：追踪你的Java行动轨迹
  • 微软 2024 最新技术全景洞察