Java教程
链表相关笔试题
本文主要是介绍链表相关笔试题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
链表面试题目
- 删除链表中给定的结点
- 链表的反转（逆置链表）
- 求链表的中间结点
- 链表的倒数第K个结点
- 链表的第一个公共结点
- 分割链表
- 回文链表
- 复杂链表的复制
删除链表中给定的结点
leetcode:删除链表中给定的结点
思路：
- 找要删除的结点；
- 改变结点的引用来删除结点（注意区分头结点的删除与非头结点删除的不同）；
代码实现：
class Solution {
public ListNode deleteNode(ListNode head, int val) {
//结点为空时
if(head==null){
return null;
}
ListNode cur=head;
ListNode prev=null; //prev标记cur的前一个结点
while(cur!=null){
if(cur.val==val){
//删除结点
//如果是头结点
if(prev==null){
head=cur.next;
cur=head;
}else{
//不是头结点
prev.next=cur.next;
cur=prev;
}
}else{
prev=cur;
cur=cur.next;
}
}
return head;
}
}
链表的反转（逆置链表）
leetcode:反转链表
思路：
借助三个引用：cur prev next；
遍历链表，同时将当前结点的指向修改为指向它的前一个引用；由于结点没有引用其前一个结点，因此必须事先保存它的前一个结点,在更改引用之前，还需要保存它的后一个结点；
代码实现：
class Solution {
public ListNode reverseList(ListNode head) {
//链表为空时
if(head==null){
return null;
}
ListNode cur=head;
ListNode prev=null; //指向当前结点的前一个
ListNode next=null; //指向当前结点的后一个
while(cur!=null){
//说明结点存在
//修改之前先保存其后一个结点
next=cur.next;
//修改引用
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
}
求链表的中间结点
leetcode：链表的中间结点
思路：
借助两个引用：fast slow；
- 两个引用均从起始位置往后走，快引用每次走两步，慢引用每次走一步；
- 当快引用走向空时，返回慢引用即可；
代码实现：
class Solution {
public ListNode middleNode(ListNode head) {
//借助快慢引用
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
//保证两步都可以走成功
fast=fast.next.next; //fast每次走两步
slow=slow.next; //slow每次走一步
}
return slow;
}
}
思考：
该题目中，当结点个数为偶数时，返回的是后一个结点，如果要返回前一个结点，怎么做？
方法：将
slow的前一个结点prev保存起来，当为偶数个结点且要返回前一个时，只需要返回prev即可；
if(fast)=null,return prev; //偶数结点
if(fast)!=null,return slow; //奇数结点
链表的倒数第K个结点
leetcode：链表的倒数第K个结点
思路：
借助两个引用：front back；
front从起始位置先走K步；front与back同时往后走，front为空时结束；back的位置刚好就是倒数第K个结点的位置；
图解：
代码实现：
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
//借助两个引用
ListNode front=head;
ListNode back=head;
//让front先往后走K步
while(0!=k){
if(front==null){
return null;
}
front=front.next;
k--;
}
//让两个引用同时走
while(front!=null){
front=front.next; //走一步
back=back.next; //走一步
}
return back;
}
}
链表的第一个公共结点
leetcode：链表的第一个公共结点
思路：
- 判断是否相交（找最后一个结点—>
遍历链表，看是否相等）； - 求交点；
由题目中已知，链表不带环，不带环的链表相交的三种情况如下所示：
代码实现：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//任意一个链表为空时，均不可能相交
if(headA==null ||headB==null){
return null;
}
//遍历链表求交点
//遍历链表A
ListNode curA=headA;
int sizeA=1;
while(curA.next!=null){
sizeA++; //遍历一个结点，sizeA增加一个
curA=curA.next;
}
//遍历链表B
ListNode curB=headB;
int sizeB=1;
while(curB.next!=null){
sizeB++;//遍历一个结点，sizeB增加一个
curB=curB.next;
}
if(curA!=curB){
return null;
}
//上面执行完，肯定会相交
//求交点
int gap=sizeA-sizeB;
curA=headA;
curB=headB;
if(gap>=0){
//A比B长
while(0!=gap--){
curA=curA.next;
}
}else{
while(0!=gap++){
curB=curB.next;
}
}
while(curA!=curB){
curA=curA.next;
curB=curB.next;
}
return curA;
}
}
分割链表
leetcode：分割链表
思路：
- 构造两个带头结点的空链表：
lessHead greatHead； lessHead用来存放小于给定值的结点，greatHead用来存大于给定值的结点；- 将
lessHead的尾结点指定greatHead的头结点即可（注意是带头的）；
代码实现：
class Solution {
public ListNode partition(ListNode head, int x) {
//链表为空时
if(head==null){
return null;
}
//将lessHead和greatHead给为带头结点的链表
ListNode lessHead =new ListNode(0); //保存小于特定值的结点
ListNode tailL= lessHead;
ListNode greatHead =new ListNode(0); //保存大于特定值的结点
ListNode tailG =greatHead;
ListNode cur=head;
while(cur!=null){
if(cur.val<x){
tailL.next=cur;
tailL=cur;
}else{
tailG.next=cur;
tailG=cur;
}
cur=cur.next;
}
//链接链接起来
//两个都带头结点，所以要指向greatHead.next
tailL.next=greatHead.next;
tailG.next=null;
return lessHead.next;
}
}
回文链表
leetcode:回文链表
思路：
- 找链表的中间结点，以中间结点将链表分割成
head1，head2两个链表； - 将后一个链表逆置；
- 依次比对两个链表的结点值是否相等；
- 将链表链接起来；
代码实现：
class Solution {
//找中间结点方法
public ListNode getMiddleNode(ListNode head){
ListNode fast=head;
ListNode slow=head;
ListNode prev=null;
//确保fast两次都可以走成功
while(fast!=null && fast.next!=null){
fast=fast.next.next;
prev=slow;
slow=slow.next;
}
if(fast==null){
return prev;
}
return slow;
}
//逆置链表
public ListNode reverseList(ListNode head){
ListNode cur=head;
ListNode next=null;
ListNode prev=null;
while(cur!=null){
//修改之前先保存next的位置
next=cur.next;
//修改引用
cur.next=prev;
prev=cur;
cur=next;
}
return prev;
}
public boolean isPalindrome(ListNode head) {
//1.找链表的中间结点
ListNode mid=getMiddleNode(head);
ListNode B=mid.next;
//2.将后一个链表进行逆置
B= reverseList(B);
//3. 依次比较两个链表的值域
ListNode curA=head;
ListNode curB=B;
boolean ret=true;
while(curA!=null && curB!=null){
if(curA.val!=curB.val){
ret=false;
break;
}
curA=curA.next;
curB=curB.next;
}
//4.将链表链表链接
B=reverseList(B);
mid.next=B;
return ret;
}
}
复杂链表的复制
leetcode：复杂链表的复制
思路：
- 在原链表的每个结点后面插入一个与原结点值相等的新结点；
- 给新插入的结点的随机引用赋值；
- 将新插入的结点断开；
插入相同结点的新链表
给每个随机引用赋值
cur在第一个结点时：
插入的结点断开
代码实现：
class Solution {
public Node copyRandomList(Node head) {
//链表为空时
if(head==null){
return null;
}
//1. 在原链表的每个结点后插入值相等的结点
Node cur=head;
while(cur!=null){
//new一个与原结点相同值域的结点
Node newNode=new Node(cur.val);
newNode.next=cur.next;
cur.next=newNode;
cur=newNode.next;
}
//2.给新插入的结点的随机引用赋值
cur=head;
while(cur!=null){
Node newNode =cur.next;
if(cur.random!=null){
newNode.random=cur.random.next;
}
cur=newNode.next;
}
//将插入结点断开
Node newHead=head.next;
cur=head;
while(cur.next!=null){
Node curNext=cur.next;
cur.next=curNext.next;
cur=curNext;
}
return newHead;
}
}
这篇关于链表相关笔试题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
2024年常用的情绪识别API01-08
-
如何利用看板工具优化品牌内容创作与审批，确保按时发布？01-07
-
百万架构师第十一课：源码分析：Spring 源码分析：Spring源码分析前篇｜JavaGuide01-07
-
质量检测标准严苛，这 6 款办公软件达标了吗？01-07
-
提升品牌活动管理的效率：看板工具助力品牌活动日历的可视化管理01-07
-
宠物商场的精准营销秘籍：揭秘看板软件的力量01-07
-
“30了，资深骑手” | 程序员能有什么好出路？01-07
-
宠物公园的营销秘籍：看板软件如何帮你精准触达目标客户？01-07
-
从任务分解到资源优化：甘特图工具全解析01-07
-
企业升级必备指南：从传统办公软件到SaaS工具的转型攻略01-07
-
一文告诉你IT项目管理如何做到高效01-07
-
好用的备忘录待办提醒APP 任务管理工具怎么选？01-07
-
如何在小团队中实现高效协作？6个关键步骤01-07
-
如何在快节奏行业中实现高效项目管理？5大实用策略01-07
-
零部件采购求精准，这 6 款办公软件匹配度咋样？01-07
栏目导航
