Table of Contents
Preface
1. Reverse a singly linked list.
2. Given a non-empty singly linked list with head node head, return the middle node of the linked list.
3. The palindrome structure of the linked list.
4. The problem of chain strap ring (*****)
4.1 Whether to wear a ring
4.2 Nodes entering the ring
5. Copy of random linked list (deep copy of linked list)
Foreword
We learned about linked lists earlier, now let’s solve some classic linked list OJ questions! ! !
1. Reverse a singly linked list.
Question link 206. Reverse linked list – LeetCode
Solution:
In this question, we defined three pointer variables. First, let prev point to NULL. The function of prev is to save the node before cur, and next is to save the node after cur.
Each loop iteration, let cur point to the previous node, that is, point to prev;
Then let prev go to the position of cur, cur to the next position, and finally let next go to the position of cur->next, thus completing a loop iteration. Until cur is NULL;
struct ListNode* reverseList(struct ListNode* head) { struct ListNode*prev = NULL; struct ListNode*cur = head; struct ListNode*next =head; while(cur) { next = cur->next; cur->next = prev; prev =cur; cur = next; } return prev; }That’s it!
2. Given a non-empty singly linked list with head node head, Returns the middle node of the linked list.
Question link: 876. The intermediate node of the linked list – LeetCode
Solution:
?
The idea of this question is actually very simple. Since we want to return to the intermediate node, then we define two pointers, fast and slow, and let fast take two steps and slow take one step. In this way, after fast has completed the journey, slow has only taken half of it.
It should be noted that when the total number of nodes is an odd number, fast will end when it reaches the last node, and when the total number of nodes is an even number, the fast node will reach NULL. Therefore, the end condition must be written as (fast & amp; & amp;fast->next).
struct ListNode* middleNode(struct ListNode* head){ struct ListNode* slow = head,*fast = head; while(fast & amp; & amp;fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
?3. The palindrome structure of the linked list.
Question link: Palindrome structure of linked list_Niuke Question Ba_Niuke.com (nowcoder.com)
?
Solution:?
This question seems complicated, but it is actually not difficult. We only need to find the middle node, then reverse the linked list from the middle node, and then traverse from the two heads respectively. If each node is equal, it is a palindrome structure.
If it is an odd number, will the number of nodes in the two linked lists not be wanted to wait?
Won’t! Because the last node of linked list A is not disconnected from the last node of linked list B, the two linked lists have a common node. Therefore, with an odd number of nodes, the number of nodes in the two linked lists is also the same. The end condition is obviously: (head & amp ;&rhead).
class PalindromeList { public: struct ListNode* reverseList(struct ListNode* head) {//Reverse linked list struct ListNode*prv = NULL; struct ListNode*cur = head; struct ListNode*n =head; while(n) { n = cur->next; cur->next = prv; prv =cur; cur = n; } return prv; } struct ListNode* middleNode(struct ListNode* head){//Find the middle node struct ListNode* slow = head,*fast = head; while(fast & amp; & amp;fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } bool chkPalindrome(ListNode* A) { ListNode* mid = middleNode(A); ListNode*rhead = reverseList(mid); while(A & amp; & amp;rhead) { if(A->val!=rhead->val) return false; A=A->next; rhead=rhead->next; } return true; } };
?
?4. The problem of linked lists with rings (*****)
The linked list loop problem is a very important type of problem in linked lists and is often encountered in corporate interviews. There are two types of problems. The first is to determine whether the linked list has a loop, and the second is to determine which node the linked list starts to enter the loop.
4.1 Whether it has a ring
Question link: 141. Ring linked list – LeetCode
Solution: We can’t help but wonder, how to determine whether a linked list has a ring?
Here we can define two pointers, fast and slow, and let fast go first. If it can still meet slow in the end, it proves that the linked list is a ring. This leads to a question, how much faster is fast than slow?
1. If slow takes one step at a time and fast takes two steps at a time, will they definitely meet?
The answer is that they will definitely meet, because the distance between fast and slow decreases by 1 every time, and will definitely reduce to 0 in the end.
2. If you take one step at a time slowly and three steps at a time fast, will you definitely meet each other?
The answer is not necessarily. If N is an even number, the distance between fast and slow decreases by 2 each time, and will eventually decrease to 0. If it is an odd number, it will eventually be reduced to -1, and a new round of pursuit will start again, and there will never be an encounter.
3. Will slow walking n steps at a time and fast walking m steps at a time definitely meet each other? (m>n>1)
Finally, we get 2L = n*C-N. We must get an odd number in the end, so we will definitely be able to catch up in the end.
bool hasCycle(struct ListNode *head) { struct ListNode* fast = head,*slow =head; while(fast & amp; & amp;fast->next) { fast =fast->next->next; slow =slow ->next; if(fast==slow) return fast; } return NULL; }
4.2 Nodes entering the ring
Question link: 142. Ring linked list II – LeetCode,
Solution: This question is different from the previous question. This question is to find the node that enters the loop and from which node it starts to enter the loop. The difficulty of this question is obviously increased compared to the previous question.
Assume that fast and slow meet at the meet point, then slow has traveled a distance of (L + X), and fast has traveled a distance of (L + n*C-X, that is to say, if one of the pointers with the same speed starts from the meeting point and the other starts from the entry point, their distance to the entrance and point is the same, so they will definitely meet at the entry point.
Therefore, the idea of this question comes out: 1. Find the meeting point 2. Let the pointers with the same speed start from the meeting point and the other from the entry point. We will meet eventually.
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow = head,*fast =head; while(fast & amp; & amp;fast->next) { slow = slow->next; fast= fast->next->next; if(slow == fast) { struct ListNode* meet= slow; while(head!=meet) { head = head->next; meet =meet->next; } return meet; } } return NULL; }
5. Copy of random linked list (deep copy of linked list)
Question link: 138. Copying a random linked list – LeetCode
Solution: Deep copying of linked lists is a difficult problem in linked lists, but if you clarify the idea, the problem will be easily solved.
Our first idea may be to copy the information of each node first, and then when we deal with the random pointing, we may use a nested loop to compare the random of each node to determine the pointing. In this way, The time complexity reaches O(N^2), which does not meet the requirements of the question.
Then I will provide a feasible idea here:
1. The copied nodes are inserted behind the original nodes (as shown in the figure)
2. Handle the random pointer
We can clearly see that the next node of the original node is the node we copied, so if the random point originally pointed to the original node and the next point of the original node can the random of the copied node complete the correct pointing, this is The problem of random pointing is solved. As shown in the figure (we have obtained all copy nodes.)
3. Unlock the copied nodes one by one and tail-insert them to get the deep-copied linked list we want.
Complete code:
truct Node* copyRandomList(struct Node* head) { struct Node* cur =head; while(cur) { struct Node*copy= (struct Node*)malloc(sizeof(struct Node)); copy->val =cur->val; copy->next = cur->next; cur->next = copy; cur=cur->next->next; } cur =head; while(cur) { struct Node*copy= cur->next; if(cur->random ==NULL) copy->random =NULL; else copy->random = cur->random->next; cur = cur->next->next; } struct Node* newhead = NULL,*fail=NULL; cur =head; while(cur) { struct Node*copy = cur->next; struct Node*next =copy->next; if(newhead==NULL) { newhead = fail = copy; } else { fail->next = copy; fail=fail->next; } cur->next = next; cur = next; } return newhead; }
Here are some classic questions about linked lists. I hope they will be helpful to you! ! !