链表经典面试题

1 回文链表

1.1 判断方法
  1. 第一种（笔试）：
    • 链表从中间分开，把后半部分的节点放到栈中
    • 从链表的头结点开始，依次和弹出的节点比较
  2. 第二种（面试）：
    • 反转链表的后半部分，中间节点的下一节点指向空
    • 两个指针分别从链表的头和尾出发比较
    • 直到左边节点到空或两个节点都到空停止
    • 判断结果出来后，要把链表后半部分反转回去。
1.2 代码实现
ublic class IsPalindromList {public static class Node {public int val;public Node next;public Node(int data) {val = data;next = null;}}public static boolean isPalindrom1(Node head) {if (head == null || head.next == null) {return true;}Stack<Node> stack = new Stack<>();Node mid = head;Node fast = head;while (fast.next != null && fast.next.next != null) {mid = mid.next;fast = fast.next.next;}while (mid.next != null) {mid = mid.next;stack.add(mid);}Node i = head;boolean ans = true;while (stack.size() != 0) {if (i.val != stack.pop().val) {ans = false;break;}i = i.next;}return ans;}public static boolean isPalindrom2(Node head) {if (head == null || head.next == null) {return true;}// 找到中间节点Node mid = head;Node fast = head;while (fast.next != null && fast.next.next != null) {mid = mid.next;fast = fast.next.next;}Node cur = mid;// 后边段链表反转Node pre = null;Node next = null;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}Node left = head;Node right = pre;boolean ans = true;while (left != null && right != null) {if (left.val != right.val) {ans = false;break;}left = left.next;right = right.next;}cur = pre;pre = null;next = null;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return ans;}public static void main(String[] args) {Node head = new Node(0);head.next = new Node(1);head.next.next = new Node(2);head.next.next.next = new Node(2);head.next.next.next.next = new Node(1);head.next.next.next.next.next = new Node(0);System.out.println(isPalindrom2(head));System.out.println(isPalindrom1(head));}}

2 荷兰国旗

链表的荷兰国旗问题，给定一个链表头节点，一个划分值

  • 把链表中小于划分值的放在左边
  • 等于划分值的放在中间
  • 大于划分值的放在右边。
2.1 解决方法

（其实我第一次写的时候第二种方法比第一种方法写的快，因为思路简单，不绕。）

  1. 第一种（笔试）：
    • 把链表的所有节点放在一个节点数组中
    • 对这个数组做partition过程
    • 之后把数组每个节点连起来
  2. 第二种（面试）：
    • 定义有六个节点，分别代表：大于、等于和小于区域的头和尾
    • 链表开始遍历，比划分值小的连在小于区域下方，同时断开节点和之前链表的关系，指向空
    • 等于和大于同理
    • 遍历完链表之后，开始把小于区域的尾巴和等于区域的头连接，等于区域的尾巴和大于区域的头连接
2.2 代码实现
public class SmallEqualBig {public static class Node {public int val;public Node next;public Node(int val) {this.val = val;next = null;}}public static Node listPartition1(Node head, int pivot) {if (head == null || head.next == null) {return head;}int index = 1;Node cur = head;while (cur.next != null) {index++;cur = cur.next;}Node[] arr = new Node[index];cur = head;for (int i = 0; i < arr.length; i++) {arr[i] = cur;cur = cur.next;}partition(arr,pivot);for (index = 1; index != arr.length; index++) {arr[index - 1].next = arr[index];}arr[index - 1].next = null;return arr[0];}public static Node listPartition2(Node head, int pivot) {if (head == null || head.next == null) {return head;}Node smallHead = null;Node smallTail = null;Node equalHead = null;Node equalTail = null;Node bigHead = null;Node bigTail = null;Node next = null;while (head != null) {next = head.next;head.next = null;if (head.val < pivot) {if (smallHead == null) {smallHead = head;smallTail = head;}else {smallTail.next = head;smallTail = smallTail.next;}} else if (head.val == pivot) {if (equalHead == null) {equalHead = head;equalTail = head;}else {equalTail.next = head;equalTail = equalTail.next;}}else {if (bigHead == null) {bigHead = head;bigTail = head;}else {bigTail.next = head;bigTail = bigTail.next;}}head = next;}if (smallTail != null) {smallTail.next = equalHead;equalTail = equalTail == null ? smallTail : equalTail;}if (equalTail != null) {equalTail.next = bigHead;}return smallHead == null ? (equalHead == null ? bigHead : equalHead) : smallHead;}private static void partition(Node[] arr, int pivot) {int small = -1;int big = arr.length;int index = 0;while (index < big) {if(arr[index].val < pivot) {swap(arr, index++, ++small);} else if (arr[index].val > pivot) {swap(arr, index++, --big);}else {index++;}}}private static void swap(Node[] arr, int i, int j) {Node temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {Node head = new Node(9);head.next = new Node(1);head.next.next = new Node(2);head.next.next.next = new Node(6);head.next.next.next.next = new Node(4);head.next.next.next.next.next = new Node(5);head.next.next.next.next.next.next = new Node(2);Node node = listPartition1(head, 2);while (node != null) {System.out.print(node.val + " ");node = node.next;}System.out.println();Node head2 = new Node(9);head2.next = new Node(1);head2.next.next = new Node(2);head2.next.next.next = new Node(6);head2.next.next.next.next = new Node(4);head2.next.next.next.next.next = new Node(5);head2.next.next.next.next.next.next = new Node(2);Node node1 = listPartition2(head2, 2);while (node1 != null) {System.out.print(node1.val + " ");node1 = node1.next;}}
}

3 复制链表

复制特殊链表，单链表中加了个rand指针，可能指向任意一个节点，也可能指向null

给定这个链表的头节点，完成链表的复制

返回复制的新链表的头节点。时间复杂度O(N),额外空间复杂度O(1)

3.1 解决方法

  1. 方法一（笔试）：

    • 用HashMap来解决，key是原数组节点，value是复制的数组节点

  2. 方式二（面试）：

    • 将复制的新节点插入到原数组的节点中，如1–>2–>3,变成1–>(copy)1–>2–>(copy)2–>3–>(copy)3

    • 复制节点的rand指针指向就是原数组的节点的rand指针的下一节点（下图所示）

    • 把复制数组拿出来的时候注意复制数组连起来还要把原数组连起来

      image-20231109141535414

3.2 代码实现
public class CopyListWithRandom {public static class Node {public int val;public Node next;public Node rand;public Node(int val) {this.val = val;}}// map方法public static Node copyListWithRandom(Node head) {if (head == null) {return null;}HashMap<Node, Node> map = new HashMap<>();Node cur = head;while (cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}Node ans = map.get(head);cur = head;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).rand = map.get(cur.rand);cur = cur.next;}return ans;}// 不借助容器public static Node copyListWithRandom2(Node head) {if (head == null) {return null;}Node cur = head;Node next = null;while (cur != null) {next = cur.next;cur.next = new Node(cur.val);cur.next.next = next;cur = next;}Node copyNode = null;cur = head;while (cur != null) {copyNode = cur.next;copyNode.rand = cur.rand == null ? null : cur.rand.next;cur = copyNode.next;}Node ans = head.next;cur = head;while (cur != null) {next = cur.next.next;copyNode = cur.next;copyNode.next = next == null ? null : next.next;cur.next = next;cur = next;}return ans;}public static void main(String[] args) {Node head = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);head.next = node2;node2.next = node3;head.rand = node3;node2.rand = head;Node node = copyListWithRandom(head);while (node != null) {System.out.println(node.val + " ");System.out.println(node == head);node = node.next;head = head.next;}}
}

4 链表相交

给定两个可能有环也可能无环的单链表，给定头节点1和头节点2.
请实现一个函数，如果两个链表相交，请返回相交的第一个节点，如果不相交，返回null
时间复杂度O(N),额外空间复杂度O(1)

4.1 解决方法
  1. 先判断两个链表是否有环
  2. 两个都无环
    • 如果两个链表的末尾节点相等，那么就是相交的，用指针先把长的链表走完两个链表的差值后，两个链表开始同时走，直到两个节点相等，就是相交的点
    • 如果末尾节点不相等，那么两个链表不相交
  3. 一个有环一个无环：两个链表不会有相交点
  4. 两个都有环
    • 判断两个链表进环的第一个节点是否是相同的
    • 相同：相交，且相交点就在无环的部分中，参考2
    • 不相同：从一个链表的入环节点开始找，如果找到了第二个链表的入环节点，那么就相交，返回两个入环节点任意一个，如果转一圈到第一个链表的入环节点还没有找到第二个入环节点，此时不相交。
4.2代码实现
public class FindFirstIntersectNode {public static class Node {public int val;public Node next;public Node(int val) {this.val = val;}}public static Node getIntersectNode(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node loop1 = getLoopNode(head1);Node loop2 = getLoopNode(head2);if (loop1 == null && loop2 == null) {return noLoop(head1, head2);}if (loop1 != null && loop2 != null) {return bothLoop(head1, loop1, head2, loop2);}return null;}private static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = head1;Node cur2 = head2;if (loop1 == loop2) {int n = 0;while (cur1.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;}else {cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop2;}cur1 = cur1.next;}return null;}}private static Node noLoop(Node head1, Node head2) {Node cur1 = head1;Node cur2 = head2;int n = 0;while (cur1.next != null) {n++;cur1 = cur2.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}cur1 = n < 0 ? head2 : head1;cur2 = cur1 == head2 ? head1 : head2;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;}private static Node getLoopNode(Node head) {if (head.next == null || head.next.next ==null) {return null;}Node slow = head.next;Node fast = head.next.next;while (fast != slow) {if (fast == null) {return null;}slow = slow.next;fast = fast.next.next;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}public static void main(String[] args) {Node head = new Node(0);head.next = new Node(1);head.next.next = new Node(2);head.next.next.next = new Node(3);head.next.next.next.next = new Node(4);head.next.next.next.next.next = head.next.next;Node head1 = new Node(0);head1.next = new Node(1);head1.next.next = new Node(2);head1.next.next.next = new Node(3);head1.next.next.next.next = new Node(4);head1.next.next.next.next.next = head.next.next.next;Node intersectNode = getIntersectNode(head, head1);System.out.println(intersectNode.val);}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/202811.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

蓝桥杯每日一题2023.11.26

蓝桥杯每日一题2023.11.26

题目描述 奖券数目 - 蓝桥云课 (lanqiao.cn) 将每一个数字进行一一枚举&#xff0c;如果检查时不带有数字4则答案可以加1 #include<bits/stdc.h> using namespace std; int ans; bool check(int n) {while(n){if(n % 10 4)return false;n / 10; }return true; } int m…
阅读更多...
C语言，通过数组实现循环队列

C语言，通过数组实现循环队列

实现循环队列最难的地方就在于如何判空和判满&#xff0c;只要解决了这两点循环队列的设计就没有问题。接下来我们将会使用数组来实现循环队列。 接下来&#xff0c;为了模拟实现一个容量为4的循环队列&#xff0c;我们创建一个容量为4 1 的数组。 接下来我们将会对这个数组…
阅读更多...
pyenv local x.xx.x不生效

pyenv local x.xx.x不生效

我本地原来有个python&#xff0c;之后用pip安装了pyenv&#xff0c;使用pyenv新安装了一个python&#xff0c;设置某个local的时候发现不生效。 这种情况需要检查3个地方。 1.有没有生成这个文件 2.需要重新开一个cmd 3.需要保证pyenv的path环境变量比之前本地的python优先…
阅读更多...
机器学习探索计划——数据集划分

机器学习探索计划——数据集划分

文章目录 导包手写数据划分函数使用sklearn内置的划分数据函数stratifyy理解举例 导包 import numpy as np from matplotlib import pyplot as plt from sklearn.datasets import make_blobs手写数据划分函数 x, y make_blobs(n_samples 300,n_features 2,centers 3,clus…
阅读更多...
【JavaSE】基础笔记 - 类和对象（上）

【JavaSE】基础笔记 - 类和对象（上）

目录 1、面向对象的初步认知 1.1、什么是面向对象 1.2、面向对象与面向过程 2. 类定义和使用 2.1、简单认识类 2.2、类的定义格式 2.3、自定义类举例说明 2.3.1、定义一个狗类 2.3.2、定义一个学生类 3、类的实例化 3.1、什么是实例化 3.2、类和对象的说明 1、面向…
阅读更多...
【腾讯云云上实验室】用向量数据库—实践相亲社交应用

【腾讯云云上实验室】用向量数据库—实践相亲社交应用

快速入口 &#x1f449;向量数据库_大模型知识库_向量数据存储_向量数据检索- 腾讯云 (tencent.com) 文章目录 前言1. 向量数据库概念及原理1.1 向量数据库概念1.2 向量数据库核心原理1.3 向量数据库优缺点1.4 向量数据库与传统数据库的区别 2. 腾讯云向量数据库的基本特性及优…
阅读更多...
51单片机IO口的四种工作状态切换

51单片机IO口的四种工作状态切换

51单片机IO口的四种工作状态切换 1.概述 这篇文章介绍单片机IO引脚的四种工作模式&#xff0c;每个模式都有各自的用武之地&#xff0c;后面在驱动外设硬件时会用它不同的模式。 2.IO口四种工作模式介绍 PnM1PnM0I/O口工作模式00准双向口&#xff1a;灌电流达20mA&#xff…
阅读更多...
进阶JAVA篇- Java 综合基本语法实践（习题一）

进阶JAVA篇- Java 综合基本语法实践（习题一）

路漫漫其修远兮&#xff0c;吾将上下而求索。—— 屈原 目录 第一道题&#xff1a;集合的灵活运用 第二道题&#xff1a;基础编程能力 第三道题&#xff1a; 手写 ArrayList 集合&#xff08;模拟实现 ArrayList 核心API&#xff09; 第四道题&#xff1a;二分查找的应用 第五道…
阅读更多...
Python 测试框架 Pytest 的入门

Python 测试框架 Pytest 的入门

简介 pytest 是一个功能强大而易于使用的 Python 测试框架。它提供了简单的语法和灵活的功能&#xff0c;用于编写和组织测试代码。 1、简单易用&#xff1a;pytest 的语法简洁明了&#xff0c;使得编写测试用例更加直观和易于理解。它使用 assert 语句来验证预期结果&#x…
阅读更多...
Java—学生信息管理系统（简单、详细）

Java—学生信息管理系统（简单、详细）

文章目录 一、主界面展示二、学生类三、系统功能方法3.1 main()方法3.2 添加学生信息3.3 删除学生信息3.4 修改学生信息3.5 查看所有学生信息 四、完整代码4.1 Student .Java4.2 StudentManger.Java 前言&#xff1a;本案例在实现时使用了Java语言中的ArrayList集合来储存数据。…
阅读更多...
Gitee上传代码教程

Gitee上传代码教程

1. 本地安装git 官网下载太慢&#xff0c;我们也可以使用淘宝镜像下载&#xff1a;CNPM Binaries Mirror 安装成功以后电脑会有Git Bush标识&#xff0c;空白处右键也可查看。 2. 注册gitee账号&#xff08;略&#xff09; 3. 创建远程仓库 4. 上传代码 4.1 在项目文件目录…
阅读更多...
Linux的基本指令（四）

Linux的基本指令（四）

目录 前言 时间相关的指令 date指令 时间戳 日志 时间戳转化为具体的时间 cal指令 find指令&#xff08;十分重要&#xff09; grep指令&#xff08;行文本过滤工具&#xff09; 学前补充 什么是打包和压缩&#xff1f; 为什么要打包和压缩&#xff1f; 怎么打包和…
阅读更多...
机器学习/sklearn笔记：MeanShift

机器学习/sklearn笔记：MeanShift

1 算法介绍 一种基于质心的算法通过更新候选质心使其成为给定区域内点的均值候选质心的位置是通过一种称为“爬山”技术迭代调整的&#xff0c;该技术找到估计的概率密度的局部最大值 1.1 基本形式 给定d维空间的n个数据点集X&#xff0c;那么对于空间中的任意点x的均值漂移…
阅读更多...
JAVA小游戏“简易版王者荣耀”

JAVA小游戏“简易版王者荣耀”

第一步是创建项目 项目名自拟 第二部创建个包名 来规范class 然后是创建类 GameFrame 运行类 package com.sxt;import java.awt.Graphics; import java.awt.Image; import java.awt.Toolkit; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; im…
阅读更多...
微信怎么关闭免密支付？正确操作方法来了！

微信怎么关闭免密支付？正确操作方法来了！

如今&#xff0c;微信已经深入到我们生活的方方面面。在享受其便利的同时&#xff0c;我们有时也会因为其提供的免密支付功能而产生焦虑和一些不必要的麻烦。 为了确保自己的支付安全&#xff0c;如果你不想继续使用这项功能&#xff0c;那么怎么关闭免密支付功能是你当前需要…
阅读更多...
CSS新手入门笔记整理：CSS基本选择器

CSS新手入门笔记整理：CSS基本选择器

id属性 id属性具有唯一性&#xff0c;也就是说&#xff0c;在一个页面中相同的id只能出现一次。在不同的页面中&#xff0c;可以出现两个id相同的元素。 语法 <div id"text"> ...... </div> class属性 class&#xff0c;顾名思义&#xff0c;就是“类…
阅读更多...
本地websocket服务端暴露至公网访问【cpolar内网穿透】

本地websocket服务端暴露至公网访问【cpolar内网穿透】

本地websocket服务端暴露至公网访问【cpolar内网穿透】 文章目录 本地websocket服务端暴露至公网访问【cpolar内网穿透】1. Java 服务端demo环境2. 在pom文件引入第三包封装的netty框架maven坐标3. 创建服务端,以接口模式调用,方便外部调用4. 启动服务,出现以下信息表示启动成功…
阅读更多...
【C++入门到精通】C++入门 —— set multiset (STL)

【C++入门到精通】C++入门 —— set multiset (STL)

阅读导航 前言一、set简介二、std::set1. std::set简介2. std::set的使用- 基本使用- std::set的模板参数列表- std::set的构造函数- std::set的迭代器- std::set容量与元素访问函数 3. set的所有函数&#xff08;表&#xff09; 三、std::multiset1. std::multiset简介 四、st…
阅读更多...
详解如何使用VSCode搭建TypeScript环境（适合小白）

详解如何使用VSCode搭建TypeScript环境（适合小白）

搭建Javascript环境 因为TypeScript不能直接在浏览器上运行。它需要编译器来编译并生成JavaScript文件。所以需要首先安装好javascript环境&#xff0c;可以参考文章&#xff1a; 详解如何使用VS code搭建JavaScript环境&#xff08;适合小白&#xff09;_vscode配置javascri…
阅读更多...
[NOIP2006]明明的随机数

[NOIP2006]明明的随机数

一、题目 登录—专业IT笔试面试备考平台_牛客网 二、代码 set去重&#xff0c;再利用vector进行排序 std::set是一个自带排序功能的容器&#xff0c;它已经按照一定的规则&#xff08;默认是元素的小于比较&#xff09;对元素进行了排序。因此&#xff0c;你不能直接对std::s…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023