当前位置：网站首页>Leetcode——链表笔试题
Leetcode——链表笔试题
2022-06-23 22:18:00 【HH~LL】
Leetcode——链表笔试题
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1. Num237 删除链表中的节点
1.1 题目描述
请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
1.2 思路
1.先判断头节点是否为待删除的节点(用while删除前面所有值为val的节点)
2.删除完头节点之后，对链表判空
3.删除链表中间值为val的节点(注意创建新节点保存原链表中的节点)
1.3 代码
public static ListNode removeElements(ListNode head, int val) {
while (head.val==val){
// 当头节点为待删除的节点时，删除头节点，直到头节点不为val
head=head.next;
}
if(head==null){
// 头节点删除完了之后，需要判空。因为有可能链表所有的节点都是待删除的节点
return null;
}else{
// 此时链表中间的节点值为待删除的节点值
ListNode prev=head;
for (ListNode cur = prev.next; cur != null ; cur=cur.next) {
if(cur.val==val){
// 此时遍历到的节点为待删除的节点，此时需要判断是否为最后一个节点
if(cur.next==null){
prev.next=null;
}else{
prev.next=cur.next;
cur.next=null;
}
}else{
prev=prev.next;
}
}
}
return head;
}
完整测试+方法代码
package List;
/** * 203. 移除链表元素 * 给你一个链表的头节点 head 和一个整数 val ， * 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 */
public class Num203_removeElements {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val; }
ListNode(int val, ListNode next) {
this.val = val; this.next = next; }
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build();
Num203_removeElements num203=new Num203_removeElements();
ListNode newhead=num203.removeElements(head,6);
System.out.println(newhead);
}
// 创建链表
public static ListNode build(){
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(6);
ListNode node4=new ListNode(3);
ListNode node5=new ListNode(4);
ListNode node6=new ListNode(5);
ListNode node7=new ListNode(6);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=node6;
node6.next=node7;
return node1;
}
public static ListNode removeElements(ListNode head, int val) {
while (head.val==val){
// 当头节点为待删除的节点时，删除头节点，直到头节点不为val
head=head.next;
}
if(head==null){
// 头节点删除完了之后，需要判空。因为有可能链表所有的节点都是待删除的节点
return null;
}else{
// 此时链表中间的节点值为待删除的节点值
ListNode prev=head;
for (ListNode cur = prev.next; cur != null ; cur=cur.next) {
if(cur.val==val){
// 此时遍历到的节点为待删除的节点，此时需要判断是否为最后一个节点
if(cur.next==null){
prev.next=null;
}else{
prev.next=cur.next;
cur.next=null;
}
}else{
prev=prev.next;
}
}
}
return head;
}
}
2.Num83删除排序链表中的重复元素
2.1 题目描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
2.2 思路
package List;
/** * 83. 删除排序链表中的重复元素 * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。 * 返回 已排序的链表 。 */
public class Num83_deleteDuplicates {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val; }
ListNode(int val, ListNode next) {
this.val = val; this.next = next; }
}
public static ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode tmp=head.next;
ListNode newhead=head;
while (tmp!=null){
while (tmp!=null && head.val==tmp.val){
tmp=tmp.next;
}
head.next=tmp;
if(tmp==null){
break;
}
head=head.next;
tmp=tmp.next;
}
return newhead;
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build();
Num83_deleteDuplicates Num83=new Num83_deleteDuplicates();
System.out.println(deleteDuplicates(head));
}
// 创建链表
public static ListNode build(){
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(1);
ListNode node3=new ListNode(2);
ListNode node4=new ListNode(3);
ListNode node5=new ListNode(3);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
return node1;
}
}
3.面试题 02.01. 移除重复节点（乱序）
3.1 题目描述
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
3.2 思路
package List;
import com.sun.xml.internal.ws.api.ha.HaInfo;
import java.util.HashMap;
import java.util.Map;
/** * 面试题 02.01. 移除重复节点 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 * 输入：[1, 2, 3, 3, 2, 1] * 输出：[1, 2, 3] * 思路： * 将遍历到的节点值（不重复）保存在哈希表中， * 当最新遍历到的节点值在哈希表中，移除 * 当不在哈希表中，向后移动 */
public class Num0201_removeDuplicateNodes {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x; }
}
public static ListNode removeDuplicateNodes(ListNode head) {
if(head==null || head.next==null){
return head;
}
Map<Integer,Integer> map=new HashMap<>();
map.put(head.val,1);
ListNode newhead=head;
ListNode tmp=head.next;
while (tmp!=null){
if(!map.containsKey(tmp.val)){
map.put(tmp.val,1);
head.next=tmp;
head=head.next;
tmp=tmp.next;
}else{
tmp=tmp.next;
}
}
head.next=null;
return newhead;
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build();
Num0201_removeDuplicateNodes Num83=new Num0201_removeDuplicateNodes();
System.out.println(removeDuplicateNodes(head));
}
// 创建链表
public static ListNode build(){
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(3);
ListNode node4=new ListNode(3);
ListNode node5=new ListNode(2);
ListNode node6=new ListNode(1);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=node6;
return node1;
}
}
4.Num206反转链表
4.1 题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
4.2 思路
4.2.1 方法1 创建新链表
创建新链表，遍历原链表，将遍历到的节点头插到新链表中。最后返回虚拟头节点的下一个节点
将遍历到的节点头插到dummyhead虚拟头节点的后面
第二个节点
package List;
/** * 206. 反转链表 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 * */
public class Num206_reverseList {
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; }
}
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null){
// 链表为空，或者链表中只有一个元素
return head;
}
// 此时链表中至少两个元素
// 创建新链表的虚拟头节点
ListNode dummyhead=new ListNode(5001);
// 遍历原链表
while (head!=null){
ListNode node=new ListNode(head.val);
node.next=dummyhead.next;
dummyhead.next=node;
head=head.next;
}
return dummyhead.next;
}
}
4.2.2 原地移动
通过改变链表的指向
public ListNode reverseList1(ListNode head) {
if(head==null || head.next==null){
// 链表为空，或者链表中只有一个元素
return head;
}
ListNode prev=null;
ListNode cur=head;
while (cur!=null){
ListNode next=cur.next;
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
5.Num876链表的中间节点
5.1 题目描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
5.2 两种思路
思路一：先遍历链表，看链表中有多少个节点count，再计算中间节点count=count/2+1;
再遍历一遍链表，每遍历一个节点，count–，当count==0时，返回
public ListNode middleNode(ListNode head) {
int count=0; // 计算链表中有多少个节点
ListNode cur=head;
while (cur!=null){
count++;
cur=cur.next;
}
count=(count/2)+1; // 计算中间节点
while (head!=null){
count--;
if(count==0){
break;
}else{
head=head.next;
}
}
return head;
}
思路2：快慢指针，定义两个指针fast low ，fast一次走两步，low一次走一步。当fast走到最后为null时，low为中间节点
public ListNode middleNode1(ListNode head) {
ListNode fast=head;
ListNode low=head;
while (fast!=null && fast.next!=null){
fast=fast.next.next;
low=low.next;
}
return low;
}
6.剑指 Offer 22. 链表中倒数第k个节点
6.1 题目描述
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
6.2 两种思路
思路1：
先遍历一遍链表计算链表中的节点个数count，
再遍历一遍链表当走到count-k+1节点时 返回
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode cur=head;
int count=0;
while (cur!=null){
count++;
cur=cur.next;
}
count=count-k+1;
while (head!=null){
count--;
if(count==0){
break;
}else{
head=head.next;
}
}
return head;
}
思路2：快慢指针
定义两个指针 fast low
fast先走K步，low再开始走，保证fast和low的相对距离为k，当fast为null时，返回low
public ListNode getKthFromEnd1(ListNode head, int k) {
ListNode fast=head;
ListNode low=head;
while (k!=0){
fast=fast.next;
k--;
}
while (fast!=null){
fast=fast.next;
low=low.next;
}
return low;
}
7.剑指 Offer II 027. 回文链表
7.1 题目描述
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
7.2 三种思路
思路1：
1.创建新链表，将原链表进行转置
2.同时遍历原链表和新建的链表，当遍历到的值不同时，return false
两个链表遍历完，return true
package List;
/** * 剑指 Offer II 027. 回文链表 * 给定一个链表的 头节点 head ，请判断其是否为回文链表。 * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 *先将链表进行反转，再判断反转后的链表和原链表是否相等 */
public class Offer027_isPalindrome {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val; }
ListNode(int val, ListNode next) {
this.val = val; this.next = next; }
}
public static boolean isPalindrome(ListNode head) {
ListNode head1=reverseList(head);
while (head1!=null){
if(head.val!=head1.val){
return false;
}
head=head.next;
head1=head1.next;
}
return true;
}
// 反转链表
public static ListNode reverseList(ListNode head){
if(head==null || head.next==null){
return head;
}
ListNode dummyhead=new ListNode(10);
while (head!=null){
ListNode node=new ListNode(head.val);
node.next=dummyhead.next;
dummyhead.next=node;
head=head.next;
}
return dummyhead.next;
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build();
Offer027_isPalindrome offer027=new Offer027_isPalindrome();
System.out.println(isPalindrome(head));
}
// 创建链表
public static ListNode build(){
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(1);
ListNode node3=new ListNode(2);
ListNode node4=new ListNode(1);
node1.next=node2;
node2.next=node3;
node3.next=node4;
return node1;
}
}
思路2
1.先找到原链表的中间节点
2.将中间节点之后的子链表进行反转
同时遍历原链表和反转后的子链表，注意便遍历满足的条件是以遍历子链表的长度
package List;
/** * 剑指 Offer II 027. 回文链表 * 给定一个链表的 头节点 head ，请判断其是否为回文链表。 * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 *先将链表进行反转，再判断反转后的链表和原链表是否相等 */
public class Offer027_isPalindrome {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val; }
ListNode(int val, ListNode next) {
this.val = val; this.next = next; }
}
public static boolean isPalindrome1(ListNode head) {
ListNode middlenode=middleNode(head);
ListNode reverse_middlenode=reverseList(middlenode);
while (reverse_middlenode!=null){
if(head.val!=reverse_middlenode.val){
return false;
}
head=head.next;
reverse_middlenode=reverse_middlenode.next;
}
return true;
}
// 反转链表
public static ListNode reverseList(ListNode head){
if(head==null || head.next==null){
return head;
}
ListNode dummyhead=new ListNode(10);
while (head!=null){
ListNode node=new ListNode(head.val);
node.next=dummyhead.next;
dummyhead.next=node;
head=head.next;
}
return dummyhead.next;
}
// 寻找链表的中间节点
public static ListNode middleNode(ListNode head){
while (head==null||head.next==null){
return head;
}
ListNode fast=head;
ListNode low=head;
while (fast.next!=null){
fast=fast.next.next;
low=low.next;
}
return low;
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build();
Offer027_isPalindrome offer027=new Offer027_isPalindrome();
System.out.println(isPalindrome1(head));
}
// 创建链表
public static ListNode build(){
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(0);
ListNode node3=new ListNode(0);
node1.next=node2;
node2.next=node3;
return node1;
}
}
思路3 将值复制到数组中后用双指针法
1.复制链表值到数组列表中。
2.使用双指针法判断是否为回文。
package List;
import java.util.ArrayList;
import java.util.List;
/** * 剑指 Offer II 027. 回文链表 * 给定一个链表的 头节点 head ，请判断其是否为回文链表。 * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 *先将链表进行反转，再判断反转后的链表和原链表是否相等 */
public class Offer027_isPalindrome {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val; }
ListNode(int val, ListNode next) {
this.val = val; this.next = next; }
}
public static boolean isPalindrome2(ListNode head) {
List<Integer> list=new ArrayList<>();
while (head!=null){
list.add(head.val);
head=head.next;
}
int left=0;
int right=list.size()-1;
while (left<right){
if(list.get(left)!=list.get(right)){
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build();
Offer027_isPalindrome offer027=new Offer027_isPalindrome();
System.out.println(isPalindrome2(head));
}
// 创建链表
public static ListNode build(){
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(0);
ListNode node3=new ListNode(0);
node1.next=node2;
node2.next=node3;
return node1;
}
}
8.Num141环形链表
8.1 题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
8.2 思路
快慢指针法：试想两个人在环形跑道跑步，一个人跑的快，一个人跑的慢，两个人总会相遇。
1.定义两个指针fast low
2.fast每次走两步，low每次走一步，条件：当fast!=null时
如果fast和low相遇，则带环
public boolean hasCycle(ListNode head) {
if(head==null){
return false;
}
ListNode fast=head;
ListNode low=head;
while (fast!=null && fast.next!=null){
fast=fast.next.next;
low=low.next;
if(fast==low){
return true;
}
}
return false;
}
9.Num21.合并两个有序链表
9.1 题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
9.2 思路
创建新链表，遍历两个链表同时比较两个链表的值大小，将值较小的链表节点尾插到新链表中。
package List;
/** * 剑指 Offer 25. 合并两个排序的链表 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 * 输入：1->2->4, * 1->3->4 * 输出：1->1->2->3->4->4 */
public class Offer25_mergeTwoLists {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x; }
}
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode dummyhead=new ListNode(101);
ListNode cur=dummyhead;
while (list1!=null || list2!=null){
if(list1!=null){
if(list2==null||(list1.val<=list2.val)){
ListNode node=new ListNode(list1.val);
dummyhead.next=node;
dummyhead=dummyhead.next;
list1=list1.next;
}else{
ListNode node=new ListNode(list2.val);
dummyhead.next=node;
dummyhead=dummyhead.next;
list2=list2.next;
}
}else if(list2!=null){
ListNode node=new ListNode(list2.val);
dummyhead.next=node;
dummyhead=dummyhead.next;
list2=list2.next;
}
}
return cur.next;
}
public static void main(String[] args) {
// 创建链表[1,2,6,3,4,5,6]
ListNode head=build1();
ListNode head1=build2();
Offer25_mergeTwoLists offer25=new Offer25_mergeTwoLists();
System.out.println(mergeTwoLists(head,head1));
}
// 创建链表
public static ListNode build1(){
ListNode node1=new ListNode(2);
return node1;
}
public static ListNode build2(){
ListNode node1=new ListNode(1);
return node1;
}
}
这样更好理解
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode dummyhead=new ListNode(101);
ListNode cur=dummyhead;
while (list1!=null && list2!=null){
if(list1.val<=list2.val){
ListNode node=new ListNode(list1.val);
dummyhead.next=node;
dummyhead=dummyhead.next;
list1=list1.next;
}else{
ListNode node=new ListNode(list2.val);
dummyhead.next=node;
dummyhead=dummyhead.next;
list2=list2.next;
}
}
if(list1==null){
dummyhead.next=list2;
}else if(list2==null){
dummyhead.next=list1;
}
return cur.next;
}
边栏推荐
- 企业网站的制作流程是什么?设计和制作一个网站需要多长时间?
- 2022 point de connaissance de l'examen des ingénieurs en sécurité de l'information: contrôle d'accès
- Stm32----- timer
- 入参参数为Object，但传递过去却成了[object object] 是因为需要转为JSON格式
- 【 GBASE的那些事儿】系列直播活动第02期《GBase 8s高可用技术及案例分析法》
- Develop synergy and efficiently manage | community essay solicitation
- PyQt5_QTableWidget分页单选右键菜单控件
- 三款很酷很骚气的底部导航
- Onsaveinstancestate callback opportunity of activity
- 【Proteus仿真】T6963C驱动PG12864示例（带中英文显示）
猜你喜欢
嵌入式接口之TIM定时器与NVIC的STM32模板库函数的一些解释
ORB_SLAM3环境搭建及demo演示
ACM. HJ89 24点运算 ●●●
高仿斗鱼 APP
再来一个高仿开眼的短视频APP
Kotlin 协程 异步 异步流
Several guesses about the design of Tencent conference number
iNFTnews | 创造者经济的未来在Web3世界中该去向何处？
Some explanations of Tim timer of embedded interface and STM32 template library function of NVIC
Task queue of laravel
随机推荐
2022 point de connaissance de l'examen des ingénieurs en sécurité de l'information: contrôle d'accès
Sorry, your USB cable may be wrong!
Facebook 开源微光效果 Shimmer
1004. 最大连续1的个数 III ●●
Idea automatically generates unit tests, doubling efficiency!
PyQt5_QTableWidget分页单选右键菜单控件
高仿斗鱼 APP
项目中常用到的 19 条 MySQL 优化
推荐4个Flutter重磅开源项目
为实现“双碳”目标，应如何实现节能、合理的照明管控
IDEA 自动生成单元测试，效率倍增！
Autofac详解
【Xilinx AX7103 MicroBalze学习笔记6】MicroBlaze 自定义 IP 核封装实验
To ensure the safety of groups with special difficulties, Guangzhou Civil Affairs made every effort to do a good job in the three prevention work
VS QT VTK 左下角显示同步小坐标轴
老龄化下背景下，综合能效管理平台为医院保驾护航
E: 无法获得锁 /var/lib/dpkg/lock
三维向量场中的通量
Construction of cache stack FIFO in different application scenarios for PLC data operation series (detailed algorithm explanation)
入参参数为Object，但传递过去却成了[object object] 是因为需要转为JSON格式