当前位置：网站首页>Linked list 2 linked list OJ problem solution and topic summary
Linked list 2 linked list OJ problem solution and topic summary
2022-07-23 05:44:00 【Liu jingyiru】
Finish this article There's an idea ：
Test site and topic It's a one to many relationship , So I think Solve more than one problem , It's the test site and topic It's a many to one relationship . Many people say that algorithm is an idea , As long as you can solve the problem . Just like you make an order , You can find more than ten sorting methods, and you can do it . But in production , Among the numerous choices, it is difficult for us to find what we can always “ winning ” The algorithm of . The final choice always weighs the pros and cons , Find the best solution ( Or in this question making state ).
Structure determines nature . Things often seem similar , But just because of this little “ different ”, To use things on the tip of a knife . Algorithm is also a very abstract thing . How many perspectives do you see things from , We can try many ways to solve . Even the learning of algorithm and data structure , Just as the task of attention at this stage , For long-term harvest , I still think it is more meaningful to study closely with knowledge points .
2. Reverse a linked list ：
Power button 
https://leetcode-cn.com/problems/remove-linked-list-elements/
The function of drawing , Make writing code more intuitive . Draw the initial , The process , End state , Write a list of variables . So we can clearly know that we need to manipulate those variables , Then draw the next step and describe it with code .
Investigation of linked list , The foundation of the foundation is “ Additions and deletions ”, It is divided into... In terms of time and space , Space
3. Look up the middle node of the list
Directly using the fast and slow pointer method to set the template may not be able to think of the fast and slow pointer method soon . By listing an expression, the essence is to describe a solution to the relationship between two variables in an expression ： The characteristic is that two variables have equality , Know one and ask one . Be careful ： The relationship here , It can be a mathematical relationship , The relationship between abstract whole and part , The relationship between the beginning and end states of an object .... wait .
The more you abstract, the more flexible you can apply . Some people often say , Speed pointer It's easy to remember . You bet , Because linked lists play with pointers . So this solution is the core in the problem solving of linked list . The later core solution will be expanded .
The lines ： Find the penultimate... In the linked list k Nodes .
21. Merge two ordered lists - Power button （LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
Empathy x=tail-k, set up x For slow pointer slow,tail For fast pointer fast, convert to k=fast-slow, Give Way fast Go ahead k Step , then fast and slow Colleague ,fast Go to the empty ,slow Go to the k. Is to use two pointers as variables in a relationship .
4. Merge two ordered lists
The idea of this question is consistent with the idea of linked list segmentation . To be added
5. Link list segmentation
Examine the subject ： The requirement is to divide a linked list by a certain number . Do not change the relative position .
Divide and rule . The idea of linked list is used here . Header interpolation is more suitable for solving the problem of creating custom linked lists , You can create a new linked list according to your needs , Insert the qualified nodes into the linked list according to the requirements .
Ideas ： take >x Insert the linked list node of into a new linked list l1. take <=x Insert the linked list node of into another new linked list l2. And then l1 And l2 Interconnected .smalltail Connected to the l2 The next node of the sentinel head node . Here, pay attention to the connection is to pay attention to the head and tail The state of the node .bigtail The last point is cur, At this time cur Point to null, So it may become a ring . Leave it empty .
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
ListNode* bigHead,*bigTail,*smallTail,*smallHead;
bigHead=bigTail=(ListNode*)malloc(sizeof(ListNode));// Create the head node of the new sentry position
smallHead=smallTail=(ListNode*)malloc(sizeof(ListNode));
ListNode* cur=pHead;
if (cur==NULL)
return NULL;
else if (cur->next==NULL)
return pHead;// Treatment of boundary conditions v
while(cur)
{
if(cur->val >=x)
{
bigTail->next=cur;
bigTail=cur;
}
else
{
smallTail->next=cur;
smallTail=cur;
}
cur=cur->next;
}
// Connect two linked lists
smallTail->next=bigHead->next;
bigTail->next=NULL;// Anti ring treatment
pHead=smallHead->next;
free(bigHead);
free(smallHead);
return pHead;
}
};6. Palindrome structure of linked list
Given a linked list, determine whether it is palindrome structure , Return to one bool value .
Power button 
https://leetcode-cn.com/problems/palindrome-linked-list/
First , Palindrome structure is a symmetrical structure . How do we prove symmetry in Mathematics ？ fold , Take the first half , Compare with the second half . Take the latter half and compare it with the left half . Or compare from both sides to the middle , Whether it is equal or not . These are three ideas .
Overall, it is divided into Find the midpoint Reverse half linked list It's worth
// Reverse the first half , Compare with the second half
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
//cur Point to the node currently to be reversed ,pre Point to cur Previous node of
ListNode cur = head, pre = null;
while (fast != null && fast.next != null){
// Check the midpoint
fast = fast.next.next;
slow = slow.next;
// Reverse a linked list
cur.next = pre; // Put the current node next Point to Previous node
pre = cur; // Previous node The assignment is Current node
cur = slow; // Current node The assignment is Next node
}
// At this time, the length of the linked list is odd , You should skip the central node
if (fast != null) slow = slow.next;
// here pre Point to the head of the inverted linked list ,slow Point to the head of the second half of the linked list , Start comparing
while (slow != null && pre != null){
if (slow.val != pre.val){
// If it's not equal , Return no
return false;
}
slow = slow.next;
pre = pre.next;
}
return true;
}
} Take the second half and reverse , Compare with the first half
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* list1=head;
ListNode* fast=list1;
// Finding the midpoint
if(fast==NULL)
return false;
while(fast!=NULL&&fast->next!=NULL)
{
list1=list1->next;
fast=fast->next->next;
}
return list1;
// Insert the new linked list after the midpoint
ListNode* newhead=NULL;
ListNode* cur=list1->next;
list1->next=NULL;
while(cur)
{
cur=cur->next;
cur->next=newhead;
newhead=cur->next;
}
return newhead;
while(newhead)
{
if(head->val!=newhead->val)
{
return false;
}
newhead=newhead->next;
head=head->next;
}
return true;
}
};7. Intersecting list 160. Intersecting list - Power button （LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
Introduction to the topic , Judge whether the two linked lists are intersecting linked lists , If yes, return the intersection node , If not , Returns an empty .
Learning enlightenment
1. Definition of intersecting linked list ： Suppose as shown in the figure N-2, By definition ,2 and 2 Can point to at the same time 3, however 3 But it can't point to 4,9, Because the same pointer cannot point to a unique address , Multiple pointers can point to the same address . So the definition should be N-1. It uses subjunctive .
2. The title contains two meanings , Judge and find nodes , So the method is limited .
analysis ： In essence, it is the feature of the intersecting linked list we know , So as to describe the definition of intersecting linked list from different angles . According to the time complexity and space complexity, we can analyze which method is better . Generally speaking ： There are as many characteristics as there are angles to analyze , Then there are many solutions .
a: Have the same next The pointer . （ The pointers of the two points point to the same ）
b: The last node is the same .（ Good to get the last node ）
3. Determine whether it is an intersecting linked list , We can consider these two perspectives ：
a: Each point in the upper chain should correspond to each point in the lower chain , Thus, it can be judged that the two points coincide .
Therefore, the worst time complexity is o(N^2).n->n Corresponding relation . The method looks violent enough , But it can be optimized M-1（ Worst case scenario ）,M-2（ General situation ） Optimization idea ： It is to optimize the worst case into a general good case , This is a way of dealing with . From the mathematical point of view, the construction method is used .
Here let the long chain go first （ The gap between short chain and long chain ）. This is the same as above “ Speed pointer ” The approach is consistent .
b: Traverse the upper chain and the lower chain respectively to find the last node , Make another judgment .
The time complexity is stable as O(N).
From the perspective of time complexity, it must be more advantageous , But according to the meaning of the question, it is best to use the optimization method a. This reflects a way of thinking . There is a saying spread on the Internet ：“ Analyze more from the perspective of time complexity ,200 After the question, there is no ordinary hand ”.
4. Sort out , We'll probably finish ：
Optimize M-1 To M-2.（ Speed pointer ）; Find the intersection （ Three situations , nothing , Normal condition , Node found ）
5. Details ： Linked list is empty. , List has only one element . This place is not handled as if else The structure of choice , Instead, it becomes Process logic structure ： Node found , Under normal circumstances, I am looking for , Did not find . But in some questions , You can't turn a variety of situations into a process logical structure , We have to discuss it separately . It can be seen that the algorithm is still popular C There are more ways for language to execute step by step ！
struct ListNode* curA=headA;
struct ListNode* curB=headB;
int lenB=0,lenA=0;
while(curA)
{
lenA++;
curA=curA->next;
}
while(curB)
{
lenB++;
curB=curB->next;
}
// Compare the length
struct ListNode* longlist=headA;
struct ListNode* shortlist=headB;
if(lenB>lenA)
{
longlist=headB;
shortlist=headA;
}
// The length of the deviation
int tag=abs(lenA-lenB);
while(tag--)
{
longlist=longlist->next;
}
// Take the same steps together , Find the intersection
while(shortlist&&longlist)
{
if(longlist==shortlist)
return shortlist;
shortlist=shortlist->next;
longlist=longlist->next;
}
return NULL;
}8. Determine if the list has links
Topic introduction , Judge whether there are links in the list .
What are the characteristics of rings ？
The ring first has a ring node , This node has two next The pointer points to it . But with the fast and slow pointer , You have to have two heads , We need breakpoints to change the structure . This is a bit of a fuss .
We find that ring structure does not violate grammatical rules , It's just , It keeps the pointer variable in an infinite loop . Use this cycle , We can dig . But this idea , I think it's hard to prove from scratch , It's not easy to think .
The range of means we can adopt is too large , Here we can also see the double pointer “ Construct relationships ” effect .
See the following question for the code .
9. Circular list
Topic introduction , Determine whether there are links in the linked list and find the entry point .
First, analyze the problem stem , Two meanings , Judge and prove .
In view of the idea of proving the intersecting linked list , Let's first observe T1, To mine the characteristics of the linked list . What comes to mind is the starting point of two pointer straight lines . But what is more obvious than this feature is that circular linked lists will cause infinite loops . Both of these ideas can be tried .
The infinite loop can be abstracted into a loop model . The verification method is not unique . Consider cycle counting , This is it Abstract the physical pursuit model . Procedures related to dead cycles , If we can find the equivalent relation , Can be used to prove the linked list .
In addition to analyzing features, we need to further analyze Factors affecting characteristics , This step of analysis will affect our analysis of some special situations . And then improve the universal solution . Here we can see T3 and T4 There are two kinds of situation analysis . The factors that affect the linked list are the size of the ring and the length in front of the ring , Why are these two factors ？？ This is not guessed by naked eye observation or lucky imagination . But because we can deduce the conclusion through the formula and then analyze the influencing factors , Draw a picture .
Learning enlightenment ：
1. Look at the picture T1, We want to use the feature of infinite acyclic ring list to prove . The model is the displacement relationship in the pursuit model . adopt Speed pointer The characteristics of flexible direction and double displacement are used to construct the relationship . The speed pointer can be seen to have a very core use in the problem of linked lists .
2. Look at the picture T3,T2, This is the conclusion prove The process .
Since the entry point is unknown , Then we need the equation containing the entry point relationship in the tabular expression . So we can take （meet） The distance to the entry point is set to X, Put the chain into the meter （head） The distance to the entry point is set to L. In tabular expressions , Try to make the situation easy to analyze .（ therefore T3 It's a diagram ） The distance of a fast pointer is twice that of a slow pointer .
2*(L+X)=N*C+X+L. Explain it. N*C： Quick pointer, every two steps , The slow pointer only takes one step , So the fast pointer must catch up with the slow pointer . And the meeting of two pointers must be at the entry point or ring . Then some people may ask why the slow pointer cannot appear N*C The situation of ？ In fact, when the fast pointer catches up with the slow pointer, it must be that the slow pointer enters the ring and the distance traveled does not exceed the ring length C Of . The maximum is C-1. Each time the fast pointer falls, the slow pointer takes one step , This step will accumulate over time , Wait for this cumulative step to reach C when , They met in circles . So the slow pointer will not go beyond C, otherwise , He is in the state of meeting . It may also be a state of never catching up . Simplify the original formula ：L=（N-1)*C+C-X;(N-1)*C You can ignore ,X Meet at point , A pointer remains slow, Another pointer returns fast, Go at the same time , The point of meeting again is the ring node .
3. verification ： We can see that our conclusion is also valid in another scenario .
Code implementation ：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode*slow,*fast;
fast=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)//fast At the end, there is no ring
return NULL;
slow=head;
while(slow!=fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
};Solution 2 ：
This solution is the first mentioned ： There is a common next node . Turn the ring problem into an intersecting linked list problem .
First , Let's assume that a fast pointer catches up with the meeting point of a slow pointer meet, And then put meet And the next node next To break off , The ring becomes an intersecting linked list , The intersection point is the ring node .
Realization ：meet The condition corresponding to the point is , Fast pointer address == Slow pointer address ;meet And next After disconnection , return next It is the head node of the lower chain . slow,fast return head, Finding intersecting nodes is what we need .
》 Method extraction
A Linked list thought
The first interpolation ： Divide and rule . Linked lists are suitable for split and reorganization operations, so some topics that need classification or local adjustment can be considered to use the split of linked lists .
B Double finger needling
Act as a variable in the relationship through double pointers . That is, describe the relationship .
Build the scene with double pointers .
There will be a double pointer topic later .
If there is a mistake , Please correct ！！
边栏推荐
- Application and grouping of regular expressions
- 按是否运行源代码划分: 静态测试和动态测试
- Day7 summary of freshman Summer Internship
- 软件测试成长之路
- Print all the words in the string array -- the story of pointer and string
- Summary of SV knowledge points
- Code random notes_ Array_ 977 square of ordered array
- Swap parity bits in binary bits
- 2021-10-25 how to jump after searching for too many boost treeview component nodes?
- 创建企业wiki，你需要知道这些
猜你喜欢
unity中3dUI或者模型始終面向攝像機，跟隨攝像機視角旋轉丨視角跟隨丨固定視角
Freshman summer internship Day6_ jigsaw puzzle
Unity摄像机画面制作全景图片|截图制作全景图
CreateProcess output redirection
anaconda 安装pytorch
Principle and implementation of Ping
OpenGL 摄像机 及阶段性复习
用队列模拟栈（C语言实现）
Day7 summary of freshman Summer Internship
VRTK功能教学（二）：Unity3DVRTK手柄瞬移和UI交互射线切换功能丨3D模型射线交互切换丨直线和曲线的切换
随机推荐
Debug No4 利用RenderDoc排查bug
使用清华镜像安装librosa
链表3 分析最优链表结构：带头双向循环链表
Get和Post的区别
Unity3d uses vrtk to configure the scene environment
Epoll use case details
按是否运行源代码划分: 静态测试和动态测试
FMETP Steam v2 使用方法（二）
JVM初探
浏览器插件损坏怎么办，删除|安装插件的方法
C language structure and linked list -- a brief answer to difficulties
FMETP Steam v2 使用方法（一）
抽象类
"Dial" out the number on the number of digits - a variety of ideas to achieve reverse output of a four digit number
CreateProcess output redirection
Code random notes_ Array_ 977 square of ordered array
What is DOM
Camera roaming
A small record of starting to blog ~
课后练习01---QQ登录