🌏引言
单链表的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _😀
🍀相交链表
🎄题目描述
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
}
}
注意,函数返回结果后,链表必须 保持其原始结构 。
🎍示例
🚩示例一
🚩示例二
🚩示例三
🎋解法思路
我们发现,两个链表如果相交
那我们就可以让长链表先走等于它们之间差值的步数
然后再同时出发,当两指针相等时,返回该节点
🚩相关变量的建立
我们将
- 长的链表用指针log表示
- 短的链表用指针sot表示
- 链表headA的长度用lenA表示
- 链表headB的长度用lenB表示
- len为lenA与LenB的差值
🚩求两链表的长度与差值
直接遍历,然后相减即可
while(log != null) {
log = log.next;
lenA ++;
}
while(sot != null) {
sot = sot.next;
lenB ++;
}
int len = lenA - lenB;
🚩确定长短链表
因为我们一开始并不知道两个链表谁长谁短,所以博主再赋初始值时,给log赋值的是headA;给sot赋值的是sot;
ListNode log = headA;
ListNode sot = headB;
判断len:
- len<0说明headB长度大于headA
- 交换log与sot,len值重置;
log = headB;
sot = headA;
len = lenB - lenA;
注意:如果len大于0,因为我们的log与sot的值已经改变,所以我们需要重新赋值
代码实现如下:
if(len < 0) {
len = lenB - lenA;
log = headB;
sot = headA;
} else {
log = headA;
sot = headB;
}
🚩长链表先走len步
while(len != 0) {
log = log.next;
len--;
}
🚩同时走,找交点
while(log != sot) {
log = log.next;
sot = sot.next;
}
🌳完整代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode log = headA;
ListNode sot = headB;
int lenA = 0;
int lenB = 0;
while(log != null) {
log = log.next;
lenA ++;
}
while(sot != null) {
sot = sot.next;
lenB ++;
}
int len = lenA - lenB;
if(len < 0) {
len = lenB - lenA;
log = headB;
sot = headA;
} else {
log = headA;
sot = headB;
}
while(len != 0) {
log = log.next;
len--;
}
while(log != sot) {
log = log.next;
sot = sot.next;
}
return log;
}
}
🍀环形链表
🎄题目描述:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
}
}
🎍 示例
🚩示例一
🚩示例二
🚩示例三
🎋思路解析:
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。
比如环形操场上跑步:
🌴扩展问题
- 为什么快指针每次走两步,慢指针走一步可以? 假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指 针的,即相遇。
快指针一次走3步,走4步,…n步行吗?
🌳完整代码:
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}
🍀环形链表||
🎄题目描述:
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
🎍示例
🚩示例一
🚩示例二
🚩示例三
🎋思路解析:
让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。
图解如下:
文章来源:https://www.toymoban.com/news/detail-669300.html
🌳完整代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
ListNode cur = head;
int count = 0;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
count = 1;
break;
}
}
if(count == 0) {
return null;
}
while(cur != slow) {
slow = slow.next;
cur = cur.next;
}
return cur;
}
}
⭕总结
关于《【数据结构】单链表面试题讲解->叁》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-669300.html
到了这里,关于【数据结构】 单链表面试题讲解->叁的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!