当前位置:网站首页>Linked list operation can never change without its roots
Linked list operation can never change without its roots
2022-07-04 10:25:00 【sqjddb】
List operation , All change is the same
- 1. Basic introduction to linked list
- 2. Headless one-way acyclic linked list
- 3. Take the lead in two-way circular list
- 4. Linked list classic topic analysis
- ① Remove linked list elements
- ② Reverse a linked list
- ③ The middle node of a list
- ④ Last in the list k Nodes
- ⑤ Integrate two ordered linked lists
- ⑥ Sort some nodes of the linked list
- ⑦ Palindrome structure of linked list
- ⑧ Public node of linked list
- ⑨ Linked list
- ⑩ Each node contains a linked list of random pointers
1. Basic introduction to linked list
A list is a kind of The physical storage structure is discontinuous 、 Out of order Storage structure , Data elements Logical order It is through... In the linked list Pointer link Sequential implementation of . In practice, the structure of linked list is very diverse , In practice, two structures are most commonly used :
- Headless unidirectional acyclic list : Simple structure , Generally, it is not used to store data alone . In fact, it is more as a substructure of other data structures , Such as hash bucket 、 Adjacency table of graph and so on .
- Take the lead in two-way circular list : The most complex structure , It's usually used to store data separately . Although the structure is complex , But there are many advantages in operation .
2. Headless one-way acyclic linked list
This is a commonly used linked list ,oj Often used in questions , Interview is also commonly used
Realize the complete program of linked list
3. Take the lead in two-way circular list
The advantage of taking the lead in two-way circular linked list is reflected in its basic operation :
Realize a leading two-way circular linked list with functions of addition, deletion and modification
4. Linked list classic topic analysis
① Remove linked list elements
Give you a list of the head node head And an integer val , Please delete all the contents in the linked list Node.val == val The node of , And back to New head node .
Answer and analysis
② Reverse a linked list
Here's the head node of the list head , Please reverse the list , And return the inverted linked list
Method 1 :
Define three pointers n1 n2 n3,n1 Record the last node location ,n2 Is the current location ,n3 Is the next node location , When modifying, the current position points to the previous position , then n1,n2,n3 All backward . Pictured :
The procedure is as follows :
struct ListNode* reverseList(struct ListNode* head){
if (!head)
return head;
struct ListNode* n1 =NULL;// Record the last node location
struct ListNode* n2 = head;// The current position
struct ListNode* n3 = head->next;// Record the next position
while (n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
Method 2 :
Traverse the nodes and insert them in turn , Make the initial tail node into a new head node
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead=NULL;
struct ListNode* cur=head;
while(cur)
{
struct ListNode* next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
③ The middle node of a list
Given a header node as 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 .
Ideas : Fast and slow pointer method , Slow pointer one step , Let's go two steps .
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* fast=head;
struct ListNode* low=head;
while(fast&&fast->next)
{
low=low->next;
fast=fast->next->next;
}
return low;
}
④ Last in the list k Nodes
Topic link
Ideas :
The fast and slow pointer method is more convenient , Let's go first k Step , Then the hands go fast and slow at the same time , Pay attention to special circumstances .
The procedure is as follows :
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
if(!pListHead)
return NULL;
struct ListNode* low=pListHead;
struct ListNode* fast=pListHead;
while(k--)
{
if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{
low=low->next;
fast=fast->next;
}
return low;
}
⑤ Integrate two ordered linked lists
Ideas : Create new header , Compare the current node values of the two linked lists , Small ones are inserted at the end of the new linked list , Connect all the rest
The procedure is as follows :
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(!l1)
return l2;
if(!l2)
return l1;
struct ListNode* newhead=NULL;
struct ListNode* tail=NULL;
struct ListNode* cur1=l1;
struct ListNode* cur2=l2;
if(cur1->val<cur2->val)
{
newhead=l1;
tail=l1;
cur1=cur1->next;
}
else
{
newhead=l2;
tail=l2;
cur2=cur2->next;
}
while(cur1&&cur2)
{
if(cur1->val<cur2->val)
{
tail->next=cur1;
tail=cur1;
cur1=cur1->next;
}
else
{
tail->next=cur2;
tail=cur2;
cur2=cur2->next;
}
}
if(cur1==NULL)
tail->next=cur2;
else
tail->next=cur1;
return newhead;
}
Tips :
The code for creating a new header is a little long , Sure Open up a sentinel node , Then start comparing directly , Finally, return the required pointer , Release sentinel node
⑥ Sort some nodes of the linked list
The head pointer of an existing linked list ListNode* pHead, Give a certain value x, Write a piece of code that will all be less than x The nodes of are arranged before the other nodes , And the original data order cannot be changed , Returns the head pointer of the rearranged linked list
Ideas : Open up two new heads , Less than x Link together , The rest are linked together , Then the two chains are linked together
The procedure is as follows :
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
while(cur)
{
if(cur->val<x)
{
lessTail->next=cur;
lessTail=cur;
}
else
{
greaterTail->next=cur;
greaterTail=cur;
}
cur=cur->next;
}
greaterTail->next=NULL;
lessTail->next=greaterHead->next;
struct ListNode* p=lessHead->next;
free(lessHead);
free(greaterHead);
return p;
}
};
⑦ Palindrome structure of linked list
For a linked list , Please design a time complexity of O(n), The extra space complexity is O(1) The algorithm of , Judge whether it is palindrome structure .
Given the head pointer of a linked list A, Please return one bool value , Represents whether it is palindrome structure . Ensure that the length of the linked list is less than or equal to 900.
Ideas : Find the middle node of the list , Reverse the last half of the chain , Traversal comparison .( May refer to ②,③)
class PalindromeList {
public:
// Find the middle node
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast=head;
struct ListNode* low=head;
while(fast&&fast->next)
{
low=low->next;
fast=fast->next->next;
}
return low;
}
// Reverse order of linked list
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newhead=NULL;
struct ListNode* cur=head;
while(cur)
{
struct ListNode* next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode * mid = middleNode(A);
struct ListNode * rhead = reverseList(mid);// The new head after the reverse order is rhead
struct ListNode *head = A;
while(head&&rhead)
{
if(head->val!=rhead->val)
return false;
head=head->next;
rhead=rhead->next;
}
return true;
}
};
⑧ Public node of linked list
Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If there is no intersection between two linked lists , return null
Ideas : First judge whether the linked list intersects , The last node of the intersecting linked list should be the same .
If it intersects , Calculate the length of the two linked lists , Define two pointers to two linked lists , Long list first take two steps of the length difference of the linked list , Then both hands go at the same time , When you go to a position in front of the public node ,next The value of is the same , find .
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
// Determine the length of the two linked lists
struct ListNode * curA = headA;
struct ListNode * curB = headB;
int lenA = 0, lenB = 0;
while(curA)
{
lenA++;
curA=curA->next;
}
while(curB)
{
lenB++;
curB=curB->next;
}
// hypothesis A Longer , If not , In exchange
struct ListNode * longList =headA;
struct ListNode * shortList =headB;
if(lenA<lenB)
{
longList=headB;
shortList=headA;
}
// Long chain takes the first step
int gap = abs(lenA-lenB);
while(gap--)
{
longList = longList->next;
}
// Go at the same time , Judge whether there is intersection
while(longList&&shortList)
{
if(longList == shortList)
{
return longList;
}
shortList = shortList->next;
longList = longList->next;
}
return NULL;
}
⑨ Linked list
a. Determine if the list has links
Given a linked list , Judge whether there are links in the list
Ideas : The speed pointer walks from the beginning at the same time , Slow pointer one step , Let's go two steps , If there are rings , The fast and slow pointers will meet
The procedure is as follows :
bool hasCycle(struct ListNode *head) {
struct ListNode* low=head;
struct ListNode* fast=head;
while(fast&&fast->next)
{
low=low->next;
fast=fast->next->next;
if(low==fast)
{
return true;
}
}
return false;
}
b. Return the ring entry position of the linked list with links
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.
Ideas :
There is a conclusion : use a Method to determine whether the linked list has a ring , If there is , You can find where the fast and slow pointers meet , Make a pointer walk step by step from where it meets , Make the other pointer walk step by step at the same time , They will eventually meet at the entrance
Proof process :
( There are many details worth thinking about in this process )
The procedure is as follows :
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* low=head;
struct ListNode* fast=head;
while(fast&&fast->next)
{
low=low->next;
fast=fast->next->next;
if(low==fast)
{
struct ListNode* meet=low;
while(meet!=head)
{
head=head->next;
meet=meet->next;
}
return meet;
}
}
return NULL;
}
⑩ Each node contains a linked list of random pointers
Give you a length of n The linked list of , Each node contains an additional random pointer random , The pointer can point to any node or null node in the list .
To construct this linked list Deep copy . The deep copy should be made exactly by n individual new Node composition , The value of each new node is set to the value of its corresponding original node . New nodes next Pointers and random The pointer in the list should also point to the new node , And make these pointers in the original linked list and the copied linked list represent the same linked list state . The pointer in the copy linked list should not point to the node in the original linked list
Ideas :
think first of , Traversal replication , But the node pointed to by the random pointer of the current position may not have been created
One method :
Insert a new node after each node , Then assign a value to the random pointer of the new node , Finally, link all the new nodes just inserted and copy successfully .
The basis of random pointer assignment : Each newly inserted node replicates the old node before it , The old node accesses another old node according to the random pointer , The new node is also inserted after the old node accessed , Old node —— Old node and New node —— New nodes The relative distance is the same , The direction of the random pointer is determined .
The procedure is as follows :
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)
return NULL;
// The copy node is behind the original node
struct Node* cur=head;
while(cur)
{
struct Node* next=cur->next;
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
cur->next=copy;
copy->next=next;
cur=next;
}
// Assign values to random nodes
cur=head;
while(cur)
{
struct Node* copy=cur->next;
if(cur->random)
{
copy->random=cur->random->next;
}
else
{
copy->random=NULL;
}
cur=copy->next;
}
// Link the new nodes
struct Node* copyhead,*copytail;
copyhead=copytail=(struct Node*)malloc(sizeof(struct Node));
cur=head;
while(cur)
{
struct Node* copy=cur->next;
struct Node* next=copy->next;
copytail->next=copy;
copytail=copy;
cur->next=next;
cur=next;
}
struct Node* p=copyhead;
copyhead=copyhead->next;
free(p);
return copyhead;
}
边栏推荐
- Mmclassification annotation file generation
- 【Day1】 deep-learning-basics
- Does any teacher know how to inherit richsourcefunction custom reading Mysql to do increment?
- 5g/4g wireless networking scheme for brand chain stores
- What is an excellent architect in my heart?
- What is devsecops? Definitions, processes, frameworks and best practices for 2022
- Dynamic address book
- 【Day1】 deep-learning-basics
- 183 sets of free resume templates to help everyone find a good job
- Use C to extract all text in PDF files (support.Net core)
猜你喜欢
Servlet基本原理与常见API方法的应用
How can Huawei online match improve the success rate of player matching
Hands on deep learning (37) -- cyclic neural network
六月份阶段性大总结之Doris/Clickhouse/Hudi一网打尽
183 sets of free resume templates to help everyone find a good job
Dynamic memory management
MPLS: multi protocol label switching
Development guidance document of CMDB
Safety reinforcement learning based on linear function approximation safe RL with linear function approximation translation 1
MySQL develops small mall management system
随机推荐
Intelligent gateway helps improve industrial data acquisition and utilization
Realsense d435 d435i d415 depth camera obtains RGB map, left and right infrared camera map, depth map and IMU data under ROS
Velodyne configuration command
如果不知道這4種緩存模式,敢說懂緩存嗎?
Hands on deep learning (41) -- Deep recurrent neural network (deep RNN)
Hands on deep learning (III) -- Torch Operation (sorting out documents in detail)
Dos:disk operating system, including core startup program and command program
Dynamic address book
System. Currenttimemillis() and system Nanotime (), which is faster? Don't use it wrong!
What are the advantages of automation?
Rhcsa learning practice
什么是 DevSecOps?2022 年的定义、流程、框架和最佳实践
5g/4g wireless networking scheme for brand chain stores
MongoDB数据日期显示相差8小时 原因和解决方案
2. Data type
System. Currenttimemillis() and system Nanotime (), which is faster? Don't use it wrong!
Hands on deep learning (39) -- gating cycle unit Gru
Hands on deep learning (46) -- attention mechanism
Golang type comparison
What is an excellent architect in my heart?