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

leetcode面试题之链表

news 来源：原创 2024/4/25 14:48:27

文章目录

    • 203. 移除链表元素
    • 206. 反转链表
    • 707. 设计链表
    • 24. 两两交换链表中的节点
    • 19. 删除链表的倒数第 N 个结点
    • 面试题 02.07. 链表相交
    • 142. 环形链表 II
    • 链表：环相关总结
        • 1、判断链表是否有环？
        • 2、怎么找环的入口？
    • 剑指 Offer 06. 从尾到头打印链表
    • 剑指 Offer 35. 复杂链表的复制
    • 剑指 Offer 18. 删除链表的节点

203. 移除链表元素

题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

链接：https://leetcode.cn/problems/remove-linked-list-elements/

思路：单链表
定义一个虚拟头结点，便于所有结点统一处理

public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head; // 初始条件判断
        ListNode dummy = new ListNode(-1, head); // 创建虚拟头结点，方便后续统一处理
        ListNode pre = dummy, cur = head;
        while (cur != null) {
            if (cur.val == val) { // 找到值相同的节点，删除
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

206. 反转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

链接：https://leetcode.cn/problems/reverse-linked-list/

思路：双指针 pre cur temp

public ListNode reverseList(ListNode head) {
         ListNode pre = null, cur = head, temp = null; // 初始化节点
         while (cur != null) {
             temp = cur.next; // 保存下一个节点
             // 翻转
             cur.next = pre;
             // 更新pre cur
             pre = cur;
             cur = temp;
         }
         return pre;
    }

707. 设计链表

题目：单链表或双链表。单链表中的节点应该具有两个属性：val 和 next，双链表再加一个pre

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

链接：https://leetcode.cn/problems/design-linked-list/

思路：链表基本操作

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    ListNode head; // 虚拟头结点
    int size; // 链表长度

    // 初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) { // 初始条件判断
            return -1;
        }
        ListNode p = head;
        for (int i = 0; i <= index; i ++) { // 这里创建了一个虚拟头结点，所以查到的是index+1位置的节点
            p = p.next;
        }
        return p.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        // 初始条件判断
        if (index > size) return;
        if (index < 0) index = 0;
       
        size ++; 
        // 找插入位置的前驱节点
        ListNode pre = head;
        for (int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        // 插入
        ListNode p = new ListNode(val); // 待插入的新节点
        p.next = pre.next;
        pre.next = p;
    }
    
    public void deleteAtIndex(int index) {
        // 初始条件判断
        if (index < 0 || index >= size) return;

        size --;
        // 找删除位置的前驱结点
        ListNode pre = head;
        for (int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        // 删除
        pre.next = pre.next.next;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

24. 两两交换链表中的节点

题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

思路：记住三个步骤

public ListNode swapPairs(ListNode head) {
        // 创建虚拟节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        // 遍历：保证当前节点和下一个节点都不为空
        while (pre.next != null && pre.next.next != null) {
            ListNode temp = head.next.next; // 记录next
            pre.next = head.next; // 步骤1
            head.next.next = head; // 步骤2
            head.next = temp; // 步骤3
            // 继续前进
            pre = head;
            head = head.next;
        }
        return dummy.next;
    }

19. 删除链表的倒数第 N 个结点

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

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

思路：双指针

  1. 定义一个虚拟头结点
  2. 定义快慢指针，快指针先走n+1步
  3. 快慢指针一起走，快指针走到尾时，慢指针刚好走到要删除位置的前驱结点
  4. 删除n位置的节点
public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 定义快慢指针
        ListNode fast = dummy, slow = dummy;
        // 快指针先走n+1步，然后快慢指针一起走，当快指针走到尾时，慢指针走到要删除指针的前一个位置
        for (int i = 0; i <= n; i ++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode pre = slow;
        // 删除第n个位置的节点
        pre.next = slow.next.next; 
        return dummy.next;
    }

面试题 02.07. 链表相交

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

思路：双指针
A B两个指针同时走，走到尾还没相交，则指向另一个链表继续走，直到相交

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        // A B两个指针同时走，走到尾还没相交，则指向另一个链表继续走，直到相交
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

142. 环形链表 II

题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null；有环则返回环的入口节点

链接：https://leetcode.cn/problems/linked-list-cycle-ii/

思路：快慢指针
1.判断是否有环
2.如果有环再找环的入口节点
（找环的入口看下面的推导思路）

public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        // 先找相交点，快指针一次走两步，慢指针一次走一步
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 相遇，快指针回到头结点开始，慢指针继续在相遇点
            if (fast == slow) {
                fast = head;
                // 同时开始都每次走一步，相遇点即为环的入口点
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

链表：环相关总结

1、判断链表是否有环？

快慢指针：快指针走两步，慢指针走一步，相交表示有环

2、怎么找环的入口？

在这里插入图片描述

1、到达相遇点时，快慢指针走的步数

慢指针：x+y ；快指针：x+y+n(y+z)

2、公式推导：

快指针一次走两步，慢指针一次走一步，所以：2*(x+y) =x+y+n(y+z)

=> x=n(y+z)-y => x = (n - 1) (y + z) + z

3、最后，快指针从头结点出发，慢指针从相遇节点继续出发，每次都走一步，此时的相遇点即为环形入口点

剑指 Offer 06. 从尾到头打印链表

题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

思路：

1.先遍历一次，求得数组长度
2.再遍历一次，用数组存储所有节点值（从尾部开始存储）
注意：第二次遍历的条件

public int[] reversePrint(ListNode head) {
        int n = 0;
        ListNode p = head;
        // 先遍历一遍，求得链表长度
        while (p != null) {
            p = p.next;
            n ++;
        }
        // 指针回到表头，再遍历一遍，将节点值存放到数组中，数组从尾开始遍历
        int[] res = new int[n];
        p = head;
        for (int i = n - 1; i >= 0; -- i) { // 注意遍历的条件
            res[i] = p.val;
            p = p.next;
        }
        return res;
    }

剑指 Offer 35. 复杂链表的复制

题目：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null

链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof

思路：哈希表 HashMap<oldNode, newNode>

  1. 第一次遍历，根据oldNode值创建newNode，建立map
  2. 第二次遍历，缺点next、random的指针指向
public Node copyRandomList(Node head) {
        // 初始判空条件
        if (head == null) return null;
        Node node = head;
        // map(node, newNode)
        Map<Node, Node> map = new HashMap<>();
        // 遍历，生成map
        while (node != null) {
            map.put(node, new Node(node.val));
            node = node.next;
        }
        // 遍历，处理next random指针
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next); // map.get(node)=newNode
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head); // 返回复制后的头结点
    }

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

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

链接：https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/

思路：

1.建立虚拟头结点，使得所有节点操作一样
2.head保存新的头结点
3.遍历，找到要删除的节点，删除并结束循环
4.最后没找到，返回头结点

public ListNode deleteNode(ListNode head, int val) {
        // 创建虚拟头结点，使得所有节点操作方式一样
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 保存一下链表的头结点
        head = dummy;
        // 遍历
        while (dummy.next != null) {
            // 找到要删除的节点，删除并结束循环
            if (dummy.next.val == val) {
                dummy.next = dummy.next.next;
                return head.next;
            }
            dummy = dummy.next;
        }
        return head.next;
    }

相关文章：

  • hi3559AV100调试记录
  • Qt5开发从入门到精通——第四篇（电子钟）
  • Vue项目搭建基础流程
  • 猿创征文｜Aixos的引入与基本使用
  • 0903（046天 线程集合总结01）
  • fatal: Unable to create ‘D:/git/2_wechat/.git/index.lock‘: File exists.
  • 网络安全原理与实践学习笔记——设计DMZ
  • 【牛客刷题】带你在牛客刷题第五弹（简单排序）
  • Fragment切换的方式介绍和一些问题的解决
  • 性能优化之图片懒加载
  • Linux多线程篇【5】——线程池
  • 指针成员操作符
  • python中应对各种机制
  • css实现时钟
  • “蔚来杯“2022牛客暑期多校训练营8 补题题解（F）
  • JS中 map, filter, some, every, forEach, for in, for of 用法总结
  • [iOS]Core Data浅析一 -- 启用Core Data
  • 【面试系列】之二：关于js原型
  • 2019.2.20 c++ 知识梳理
  • classpath对获取配置文件的影响
  • Laravel5.4 Queues队列学习
  • Linux Process Manage
  • node.js
  • vue--为什么data属性必须是一个函数
  • webgl （原生）基础入门指南【一】
  • 第2章 网络文档
  • 更好理解的面向对象的Javascript 1 —— 动态类型和多态
  • 看域名解析域名安全对SEO的影响
  • 融云开发漫谈：你是否了解Go语言并发编程的第一要义？
  • 实现简单的正则表达式引擎
  • 通过git安装npm私有模块
  • 一份游戏开发学习路线
  • Nginx惊现漏洞 百万网站面临“拖库”风险
  • 阿里云ACE认证学习知识点梳理
  • 回归生活：清理微信公众号
  • 进程与线程（三）——进程/线程间通信
  • ​html.parser --- 简单的 HTML 和 XHTML 解析器​
  • ​人工智能书单（数学基础篇）
  • ​水经微图Web1.5.0版即将上线
  • %3cli%3e连接html页面,html+canvas实现屏幕截取
  • （C#）if (this == null)？你在逗我，this 怎么可能为 null！用 IL 编译和反编译看穿一切
  • （Redis使用系列） Springboot 实现Redis 同数据源动态切换db 八
  • （四）搭建容器云管理平台笔记—安装ETCD(不使用证书)
  • （译）计算距离、方位和更多经纬度之间的点
  • .bashrc在哪里，alias妙用
  • .NET 4 并行（多核）“.NET研究”编程系列之二 从Task开始
  • .NET CORE 3.1 集成JWT鉴权和授权2
  • .NET Core IdentityServer4实战-开篇介绍与规划
  • .NET 线程 Thread 进程 Process、线程池 pool、Invoke、begininvoke、异步回调
  • .NET 依赖注入和配置系统
  • .NET/ASP.NETMVC 深入剖析 Model元数据、HtmlHelper、自定义模板、模板的装饰者模式（二）...
  • .NET/C# 避免调试器不小心提前计算本应延迟计算的值
  • ：“Failed to access IIS metabase”解决方法
  • ；号自动换行
  • @property括号内属性讲解