当前位置：网站首页>链表面试题(图文详解)
链表面试题(图文详解)
2022-07-06 07:34:00 【影子，你陪着我累吗？】
写在前面：
博主主页：戳一戳，欢迎大佬指点！
博主秋秋：QQ：1477649017 欢迎志同道合的朋友一起加油喔
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个小菜鸟嘿嘿
-----------------------------谢谢你这么帅气美丽还给我点赞！比个心-----------------------------
面试经典例题
1，删除链表中所有等于定值val的节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;//链表为空
}
ListNode prev = head;
ListNode cur = head.next;
while(cur != null){
if(cur.val == val){
cur = cur.next;
prev.next = cur;
}else{
prev = cur;
cur = cur.next;
}
}
//特殊情况，头节点也为key
if(head.val == val){
head = head.next;
}
return head;
}
}
这个题的解答其实和我们的单链表的模拟实现的removeAllKey()是一个意思，所以具体的解析大家看这张图。
2，反转一个单链表
//要求原地进行反转
//1,只用一个节点指针，进行头插
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}
}
//2，两个节点指针，原地逆序
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode prev = head;
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
head = prev;
return head;
}
}
【图示：第一种方法】
【图示：第二种方法】
3，寻找中间节点
具体题目：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
可能有的同学会觉得很简单，先遍历一遍求出长度，然后不就顺理成章的知道中间节点了嘛。但是，面试题的要求肯定不会让你如此，假如要求你只能遍历一遍就把问题解决，那你如何做呢？
//这里用到了 快慢指针 的思想
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
【图示：】
这里解释一下快慢指针的原理，因为它是找到中间节点，我们的fast与slow指针的起点一样，路程也一样，但是fast的速度是slow的二倍，这样当我们的fast走到终止时，slow的位置就是我们要求的中间节点。
4，链表中倒数第K个节点
//要求还是只让你遍历一遍链表
import java.util.*;
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null){
return null;
}
if(k <= 0){
//判断k的合法性
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k - 1 != 0){
//让fast先走k-1步
fast = fast.next;
if(fast == null){
return null;//说明k过大
}
k--;
}
while(fast.next != null){
//fast.next == null 就说明fast到了最后节点了，就不走了
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
这个题还是快慢指针的思想。它既然想找到我们的倒数第k个节点，我们就想让fast先走k-1步，这样的话，等到fast到最后一个节点时，slow的位置就是我们的倒数第k个节点处。这里的关键就是我们的倒数第k个节点与我们的最后一个节点之间差的就是k-1步，这也是为什么要将fast先走k-1步的原因。
【图示：】
while(k - 1 != 0){
//让fast先走k-1步
fast = fast.next;
if(fast == null){
return null;//说明k过大
}
k--;
}
这里还有一个点就是我们的k肯定是不能大于我们的链表长度的，但是要求是只能遍历一遍链表，所以我们没办法去求链表的长度，但是我们知道，限制k不能过大的原因就是fast走的时候可能直接变成null了，所以我们可以把这个条件转换到这里的先走k-1步中，因为假设我们的链表长度是len，那么极端情况就是求倒数第len个，那么fast最多先走len-1步，所以如果当k> size()的时候，k-1 >= size()，明显就不符合了，fast在移动的过程中就会变成null，这个时候就说明k过大了。
5，合并两个有序链表
具体题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newNode = new ListNode(-1);//虚拟节点
ListNode tmp = newNode;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
tmp.next = list1;
tmp = list1;
list1 = list1.next;
}else{
tmp.next = list2;
tmp = list2;
list2 = list2.next;
}
}
if(list1 == null){
//也包含初始条件下某一个就为null的情况
tmp.next = list2;
}
if(list2 == null){
tmp.next = list1;
}
return newNode.next;//然会新的头节点，原两个链表的头节点都动了
}
}
看到这个题呢，可能很多同学会想起合并两个有序数组，这二者之间确实有着异曲同工之妙，不一样的是这里我不需要额外的空间，因为链表我可以直接改变next域让其串起来，即使是两个链表的元素。同样是指针遍历，list1,list2两个节点指针去遍历元素，tmp记录当前所在元素的位置。
【图示：】
6，分割链表
具体题目：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
import java.util.*;
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode as = null;
ListNode ae = null;
ListNode bs = null;
ListNode be = null;
ListNode cur = pHead;
while(cur != null){
if(cur.val < x){
if(as == null){
//可能是放入第一个数据
as = cur;
ae = cur;
}else{
ae.next = cur;
ae = ae.next;
}
}else{
if(bs == null){
bs = cur;
be = cur;
}else{
be.next = cur;
be = be.next;
}
}
cur = cur.next;
}
//然后把两个段链接起来
if(as == null){
//有可能没有第一段
return bs;//bs也有可能是null
}
ae.next = bs;//把两段连起来，如果第二段不存在，刚好用来把第一段结尾置为null
if(bs != null){
//如果存在第二段，那么第二段的尾巴需要手动置null一下
be.next = null;
}
return as;
}
}
【图示：】
7，链表的回文结构
import java.util.*;
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head == null){
return true;//空链表算回文
}
ListNode fast = head;
ListNode slow = head;
//先找到中间节点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//从中间后进行链表的翻转
ListNode cur = slow.next;
while(cur != null){
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//翻转完毕，slow现在在最后一个节点处
while(head != slow){
if(head.val != slow.val){
return false;
}
if(head.next == slow){
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}
回文结构，按照面试的要求，肯定是不能用除链表之外的空间的，所以你只能原地判断。那想法肯定是前后遍历然后对比值，但是链表如何能够从后往前走呢？此时反转是不是就可以达到目的了，所以我们的思路就是
1，找到中间节点 2，从中间节点往后开始反转链表 3，判断回文。
【图示：】
8，相交链表的公共节点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode fast = headA;//fast指向的是长的那个链表，现在假设是headA长
ListNode slow = headB;
int subLen = 0;
int lenA = 0;
int lenB = 0;
while(fast != null){
lenA++;//从headA计算长度
fast = fast.next;
}
while(slow != null){
lenB++;//从headB计算长度
slow = slow.next;
}
subLen = lenA - lenB;
//因为动了fast与slow，现在重新让他们指向开头，同时更新一下fast与slow的指向
if(subLen < 0){
fast = headB;
slow = headA;
subLen = lenB - lenA;
}else{
fast = headA;
slow = headB;
}
while(subLen != 0){
//让长的那一方的指针fast先走差值步
fast = fast.next;
subLen--;
}
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
首先我们得弄清楚一个点，两个链表相交，是怎么相交？ X 型 或者是 Y型？答案肯定是 Y型，因为我们的链表一个节点的后继肯定只有一个，所以不肯能是X型。
【图示：】
9，判断链表中是否有环
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;
}
}
可以看到，原理还是很简单，快慢指针的追及问题，因为如果有环存在，那么在快指针与慢指针的移动过程中，一定会相遇。但是，这里有一个关键问题就是，快指针与慢指针之间的速度差是多少？怎么确定？
答案是：快指针一次走两步，慢指针一次走一步。原因如下：
快指针肯定是先进环，慢指针后进环，那么这个时候，最好的情况就是刚好slow过来就直接和fast相遇了；最差的情况就是二者之间刚好差一个环的长度。fast指针每次走两步，slow指针每次走一步，那么每移动一次，二者之间的距离就会少一步(相对于slow，fast的每次移动都多一步，所以移动一次，中间距离就会缩小一步)，这个时候其实就是一个fast去追slow的问题，并且不会出现套圈的问题。所以，在slow把这圈走完之间，fast绝对可以把slow追上。
可能有的同学会问快指针可不可以一次走3步，或者4步，或者更多？其实我们一次只走两步，这个决定的考量就是为了防止套圈的问题出现，因为快慢指针之间的速度差越大，在某种程度上，可能会更加快的追上，但同时套圈的危险性就更大了，比如：
注意，我们是两个都走完了才开始比，移动过程中的相遇是不算的，综上，就是我们选择走两步与走一步的原因。
10，返回入环节点
具体题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
//奇数个节点或者偶数个节点没环的终止条件
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast == null || fast.next == null){
//说明没有环
return null;
}
//上面没有return掉，就说明有环，并且fast与slow相遇了
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
【图示：】
最后，今天的文章分享比较简单，就到这了，如果大家觉得还不错的话，还请帮忙点点赞咯，十分感谢！🥰🥰🥰
边栏推荐
- [online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
- 杰理之需要修改 gatt 的 profile 定义【篇】
- [JDBC] quick start tutorial
- Opencv learning notes 8 -- answer sheet recognition
- 【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
- Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
- Simulation of holographic interferogram and phase reconstruction of Fourier transform based on MATLAB
- datax自检报错 /datax/plugin/reader/._drdsreader/plugin.json]不存在
- When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
- [window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
猜你喜欢
Go learning -- implementing generics based on reflection and empty interfaces
Detailed explanation | detailed explanation of internal mechanism of industrial robot
leecode-C語言實現-15. 三數之和------思路待改進版
Do you really think binary search is easy
![Ble of Jerry [chapter]](/img/ed/32a5d045af8876d7b420ae9058534f.png)
Ble of Jerry [chapter]
SSM learning
Compliance and efficiency, accelerate the digital transformation of pharmaceutical enterprises, and create a new document resource center for pharmaceutical enterprises
杰理之开发板上电开机，就可以手机打开 NRF 的 APP【篇】
Redis builds clusters
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
随机推荐
mysql如何合并数据
洛谷P1836 数页码 题解
Leecode-c language implementation -15 Sum of three ----- ideas to be improved
Compliance and efficiency, accelerate the digital transformation of pharmaceutical enterprises, and create a new document resource center for pharmaceutical enterprises
NiO programming introduction
Three no resumes in the software testing industry. What does the enterprise use to recruit you? Shichendahai's resume
Supervisor usage document
Games101 Lesson 7 shading 1 Notes
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
烧录场景下的源代码防泄密方案分享
杰理之BLE【篇】
Simulation of Michelson interferometer based on MATLAB
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
Markdown 中设置图片图注
ORACLE列转行--某字段按指定分隔符转多行
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
Opencv learning notes 8 -- answer sheet recognition
Jerry needs to modify the profile definition of GATT [chapter]
[MySQL learning notes 29] trigger
Twelve rules for naming variables