当前位置：网站首页>Linked list interview questions (Graphic explanation)
Linked list interview questions (Graphic explanation)
2022-07-06 07:36:00 【Shadow, are you tired with me?】
Write it at the front ：
Blogger Homepage ： To poke , Welcome the big guy to give directions ！
Blogger Qiu ：QQ：1477649017 Welcome like-minded friends to come on
Goal dream ： Enter the large factory , Determined to be a cow breaking Java Program the ape , Although he is still a little rookie now, hehe
----------------------------- Thank you for being so handsome and beautiful. Give me some praise ！ More than a heart -----------------------------
Classic example of interview
- 1, Delete all values equal to the fixed value in the linked list val The node of
- 2, Invert a single chain table
- 3, Find intermediate nodes
- 4, Last in the list K Nodes
- 5, Merge two ordered lists
- 6, Split the list
- 7, Palindrome structure of linked list
- 8, The public node of the intersecting linked list
- 9, Judge whether there are links in the list
- 10, Return to the ring node
1, Delete all values equal to the fixed value in the linked list val The node of
Leetcode Portal , Click here ！！
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;// Linked list is empty.
}
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;
}
}
// A special case , The head node is also key
if(head.val == val){
head = head.next;
}
return head;
}
}
The solution of this problem is actually the same as the simulation of our single linked list removeAllKey() It means the same thing , So for specific analysis, let's see this picture .
2, Invert a single chain table
Leetcode Portal , Click here ！！
// It is required to reverse in place
//1, Use only one node pointer , Perform head insertion
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, Two node pointers , In reverse order
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;
}
}
【 Icon ： The first method 】
【 Icon ： The second method 】
3, Find intermediate nodes
Specific topic ： Given a node with a header head The non empty single chain table of , Returns the middle node of the linked list . If there are two intermediate nodes , Then return to the second intermediate node
Leetcode Portal , Click here ！！
Some students may feel very simple , First traverse to find the length , Then it's natural to know the intermediate node . however , The requirements of the interview questions will definitely not make you so , If it is required that you can only traverse once to solve the problem , Then how do you do it ？
// It's used here Speed pointer Thought
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;
}
}
【 Icon ：】
Here is an explanation of the principle of the fast and slow pointer , Because it finds the intermediate node , our fast And slow The starting point of the pointer is the same , The journey is the same , however fast The speed of slow Double of , This is what we are fast When it comes to the end ,slow The position of is the intermediate node we require .
4, Last in the list K Nodes
// It is required that you only traverse the linked list
import java.util.*;
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null){
return null;
}
if(k <= 0){
// Judge k Legitimacy
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k - 1 != 0){
// Give Way fast Go ahead k-1 Step
fast = fast.next;
if(fast == null){
return null;// explain k Too big
}
k--;
}
while(fast.next != null){
//fast.next == null Just explain fast It's the last node , I won't go
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
This question is still the idea of speed pointer . Since it wants to find our penultimate k Nodes , We just want fast Go ahead k-1 Step , In this case , wait until fast To the last node ,slow The position of is our penultimate k At nodes . The key here is our penultimate k The difference between nodes and our last node is k-1 Step , That's why fast Go ahead k-1 The reason for step .
【 Icon ：】
while(k - 1 != 0){
// Give Way fast Go ahead k-1 Step
fast = fast.next;
if(fast == null){
return null;// explain k Too big
}
k--;
}
There is another point here, which is our k It must not be longer than our linked list , But the requirement is that you can only traverse the linked list once , So we can't find the length of the linked list , But we know that , Limit k The reason why it can't be too big is fast When you leave, you may directly become null 了 , So we can change this condition to go first k-1 In step , Because suppose the length of our linked list is len, Then the extreme case is to find the penultimate len individual , that fast At most, go first len-1 Step , So if you are k> size() When ,k-1 >= size(), Obviously, it doesn't meet ,fast In the process of moving, it will become null, At this time, it means k Too big .
5, Merge two ordered lists
Specific topic ： Merge two ordered lists into a new ordered list and return . The new linked list is made up of all the nodes of the given two linked lists .
Leetcode Portal , Click here ！！
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newNode = new ListNode(-1);// Virtual node
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){
// It also includes that one of the initial conditions is null The situation of
tmp.next = list2;
}
if(list2 == null){
tmp.next = list1;
}
return newNode.next;// There will be new header nodes , The head nodes of the original two linked lists have moved
}
}
See this question , Many students may think of merging two ordered arrays , There are indeed similarities between the two , The difference is that I don't need extra space here , Because I can change the linked list directly next Let the fields string , Even the elements of two linked lists . It is also pointer traversal ,list1,list2 Two node pointers to traverse the element ,tmp Record the current location of the element .
【 Icon ：】
6, Split the list
Specific topic ： Write code , At the given value x Divide the list into two parts , All less than x The node rank of is greater than or equal to x Before the node of .
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){
// It may be to put the first data
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;
}
// Then link the two paragraphs
if(as == null){
// There may be no first paragraph
return bs;//bs It could be null
}
ae.next = bs;// Connect the two sections , If the second paragraph does not exist , It's just used to set the end of the first paragraph as null
if(bs != null){
// If there is a second paragraph , Then the tail of the second segment needs to be set manually null once
be.next = null;
}
return as;
}
}
【 Icon ：】
7, Palindrome structure of linked list
import java.util.*;
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head == null){
return true;// Empty linked list calculation palindrome
}
ListNode fast = head;
ListNode slow = head;
// First find the middle node
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
// Flip the linked list from the middle
ListNode cur = slow.next;
while(cur != null){
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// Flip over ,slow Now at the last node
while(head != slow){
if(head.val != slow.val){
return false;
}
if(head.next == slow){
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}
Palindrome structure , According to the requirements of the interview , You must not use space other than the linked list , So you can only judge in situ . The idea must be to iterate back and forth and then compare the ratio , But how can the linked list go forward from the back ？ At this point, whether the reversal can achieve the goal , So our idea is
1, Find the middle node 2, Reverse the linked list from the middle node 3, Palindrome .
【 Icon ：】
8, The public node of the intersecting linked list
Leetcode Portal , Click here ！！
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode fast = headA;//fast It points to the long linked list , Now suppose headA Long
ListNode slow = headB;
int subLen = 0;
int lenA = 0;
int lenB = 0;
while(fast != null){
lenA++;// from headA Calculate the length
fast = fast.next;
}
while(slow != null){
lenB++;// from headB Calculate the length
slow = slow.next;
}
subLen = lenA - lenB;
// Because it moved fast And slow, Now let them point to the beginning again , At the same time, update fast And slow The direction of
if(subLen < 0){
fast = headB;
slow = headA;
subLen = lenB - lenA;
}else{
fast = headA;
slow = headB;
}
while(subLen != 0){
// Let the long side of the pointer fast Take the first step
fast = fast.next;
subLen--;
}
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
First of all, we have to make one point clear , Two linked lists intersect , How to intersect ？ X type Or is it Y type ？ The answer must be Y type , Because there must be only one successor of a node in our linked list , So it can't be X type .
【 Icon ：】
9, Judge whether there are links in the list
Leetcode Portal , Click here ！！
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
// The termination condition of odd or even nodes without ring
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
}
You can see , The principle is still very simple , Fast and slow pointer tracking and problem , Because if there is a ring , Then in the process of moving the fast pointer and the slow pointer , We will meet . however , There is a key problem here , What is the speed difference between the fast pointer and the slow pointer ？ How to determine ？
The answer is ： Go two steps at a time , Slow pointer one step at a time . Here's why ：
The fast pointer must be the advanced ring , Slow pointer backward loop , So at this point , The best case is just slow Just come over and talk to fast Met ; The worst case is that there is just a difference in the length of a ring between them .fast Two steps at a time ,slow One step at a time , So every time you move , The distance between the two will be less ( be relative to slow,fast Every time you move, one more step , So move once , The middle distance will be reduced by one step ), This time is actually a fast Go after slow The problem of , And there will be no ferrule problem . therefore , stay slow Between walking this circle ,fast You can definitely put slow Catch up .
Some students may ask if the fast pointer can walk at one time 3 Step , perhaps 4 Step , Or more ？ In fact, we only take two steps at a time , The consideration of this decision is to Prevent ferrule There's something wrong with , Because the greater the speed difference between fast and slow pointers , In a way , It may catch up faster , But at the same time, the danger of ferrule is even greater , such as ：
Be careful , It was after both of us finished walking that we began to compare , Meeting in the process of moving is not counted , Sum up , That is why we choose to take two steps and one step .
10, Return to the ring node
Specific topic ： Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to NULL.
Leetcode Portal , Click here ！！
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){
// The termination condition of odd or even nodes without ring
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast == null || fast.next == null){
// No ring
return null;
}
// There is no return fall , It means there are rings , also fast And slow Met
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
【 Icon ：】
Last , Today's article sharing is relatively simple , That's it , If you think it's good , Please help me to praise , Thank you very much. ！🥰🥰🥰
边栏推荐
- TypeScript void 基础类型
- Three treasures of leeks and Chinese men's football team
- Scala语言学习-08-抽象类
- http缓存，强制缓存，协商缓存
- Scala language learning-08-abstract classes
- Methods for JS object to obtain attributes (. And [] methods)
- Simple and understandable high-precision addition in C language
- 剪映的相关介绍
- word设置目录
- js對象獲取屬性的方法(.和[]方式)
猜你喜欢
Simulation of Teman green interferometer based on MATLAB
杰理之BLE【篇】
Key value judgment in the cycle of TS type gymnastics, as keyword use
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
Typescript interface and the use of generics
学go之路（一）go的基本介绍到第一个helloworld
Redis builds clusters
![Ble of Jerry [chapter]](/img/ed/32a5d045af8876d7b420ae9058534f.png)
Ble of Jerry [chapter]
![[1. Delphi foundation] 1 Introduction to Delphi Programming](/img/14/272f7b537eedb0267a795dba78020d.jpg)
[1. Delphi foundation] 1 Introduction to Delphi Programming
JDBC learning notes
随机推荐
How to delete all the words before or after a symbol in word
How can word delete English only and keep Chinese or delete Chinese and keep English
【mysql学习笔记29】触发器
Force buckle day31
The way to learn go (II) basic types, variables and constants
杰理之普通透传测试---做数传搭配 APP 通信【篇】
Typescript function definition
成为优秀的TS体操高手 之 TS 类型体操前置知识储备
http缓存，强制缓存，协商缓存
Jerry's ad series MIDI function description [chapter]
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
Le chemin du navigateur Edge obtient
word中如何删除某符号前面或后面所有的文字
[1. Delphi foundation] 1 Introduction to Delphi Programming
js對象獲取屬性的方法(.和[]方式)
杰理之BLE【篇】
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
Generator Foundation
杰理之BLE【篇】
TypeScript 接口属性