当前位置：网站首页>链表面试题(图文详解)
链表面试题(图文详解)
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;
}
}
【图示：】
最后，今天的文章分享比较简单，就到这了，如果大家觉得还不错的话，还请帮忙点点赞咯，十分感谢！🥰🥰🥰
边栏推荐
- Markdown 中设置图片图注
- How to delete all the words before or after a symbol in word
- 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
- Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
- Supervisor usage document
- 可变参数重载时的内存错误
- Detailed explanation | detailed explanation of internal mechanism of industrial robot
- Twelve rules for naming variables
- Solution to the problem of breakthrough in OWASP juice shop shooting range
- 【MySQL学习笔记32】mvcc
猜你喜欢
ORACLE列转行--某字段按指定分隔符转多行
QT color is converted to string and uint
![Ble of Jerry [chapter]](/img/ce/127b597cdd238bb0c37326f5cf8265.png)
Ble of Jerry [chapter]
![Ble of Jerry [chapter]](/img/ed/32a5d045af8876d7b420ae9058534f.png)
Ble of Jerry [chapter]
leecode-C语言实现-15. 三数之和------思路待改进版
Ali's redis interview question is too difficult, isn't it? I was pressed on the ground and rubbed
数字经济时代，如何保障安全？
Markdown 中设置图片图注
How to delete all the words before or after a symbol in word
![[cf gym101196-i] waif until dark network maximum flow](/img/66/6b339fc23146b5fbdcd2a1fa0a2349.png)
[cf gym101196-i] waif until dark network maximum flow
随机推荐
C ＃ connect to SQLite database to read content
【MySQL学习笔记32】mvcc
Mise en œuvre du langage leecode - C - 15. Somme des trois chiffres - - - - - idées à améliorer
[MySQL learning notes 32] mvcc
Ble of Jerry [chapter]
The way to learn go (I) the basic introduction of go to the first HelloWorld
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
CF1036C Classy Numbers 题解
leecode-C语言实现-15. 三数之和------思路待改进版
OpenJudge NOI 2.1 1749:数字方格
TS 类型体操 之 循环中的键值判断,as 关键字使用
Basics of reptile - Scratch reptile
Typescript interface properties
Detailed explanation | detailed explanation of internal mechanism of industrial robot
[MySQL learning notes 29] trigger
word设置目录
Significance and measures of encryption protection for intelligent terminal equipment
TypeScript 变量作用域
Résumé de la structure du modèle synthétisable
Sélectionnez toutes les lignes avec un symbole dans Word et changez - les en titre