Shulou(Shulou.com)06/01 Report--

This article mainly shows you "what are the C++ list exercises?" the content is simple and clear. I hope it can help you solve your doubts. Now let the editor lead you to study and learn the article "what are the C++ list exercises?"

Reverse single linked list

Topic 1: give you the header node head of the single linked list, please reverse the linked list and return to the reversed linked list.

Example 1:

Input: head = [1, 2, 3, 4, 5]

Output: [5, 4, 4, 3, 2, 1]

Source of topic: force buckle

Idea 1: flip the pointer direction, first we need to have three pointers, this will not show the code, the logical process is as follows:

Idea 2: head insertion method, we take down each node for head insertion implementation! The code is implemented as follows:

Struct ListNode* reverseList (struct ListNode* head) {struct ListNode* cur = head; struct ListNode* newHead = NULL; while (cur) {struct ListNode* next = cur- > next; / / header cur- > next = newHead; newHead = cur; cur = next } return newHead;} returns the location of the middle node of the linked list

Topic 2: given a non-empty single linked list whose header node is head, return the middle node of the linked list.

If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input: [1, 2, 3, 4, 5, 6]

Output: node 4 in this list (serialized form: [4, 5, 5, 6])

Since the list has two intermediate nodes with values of 3 and 4, we return to the second node

Source of topic: force buckle

Idea: we use the method of fast and slow pointers, fast pointer fast takes two steps, slow pointer slow takes one step, so that when fast is finished, slow pointer goes to the middle position, but we should note that if the linked list node is odd, then when fast is NULL, it should end the loop, if the linked list node is even, then when fast- > next is NULL, then end the loop! The idea is parsed, and the code is implemented as follows:

Struct ListNode* middleNode (struct ListNode* head) {struct ListNode* slow = head, * fast = head; while (fast & & fast- > next) {slow = slow- > next; fast = fast- > next- > next;} return slow;} merge two ordered linked lists

Topic 3: merge two ascending linked lists into a new ascending linked list and return. The new linked list is formed by splicing all the nodes of the given two linked lists.

Example 1:

Input: L1 = [1Magol 2pr 4], L2 = [1BI 3pr 4]

Source of topic: force buckle

Idea: first of all, we have to determine whether the two linked lists are empty, and if so, return another linked list! Then we need to define two pointer head and a tail pointer tail, and then we compare whether list1- > val is greater than list2- > val and then do the linked list operation, and when one of the linked list is empty, then jump out of the loop, we need to determine again outside the loop which list is empty to cause the jump out of the loop, and finally link the non-empty list at the back! Finally, go back to the pointer head!

Friends are advised to look at this idea and try to write it on their own, you can refer to the following code:

Struct ListNode* mergeTwoLists (struct ListNode* list1, struct ListNode* list2) {if (list1 = = NULL) return list2; if (list2 = = NULL) return list1; struct ListNode* head = NULL, * tail = NULL; if (list1- > val

Val) {head = tail = list1; list1 = list1- > next;} else {head = tail = list2; list2 = list2- > next;} while (list1! = NULL & & list2! = NULL) {if (list1- > val)

Val) {/ / tail- > next = list1; list1 = list1- > next;} else {tail- > next = list2; list2 = list2- > next } tail = tail- > next;} if (list1) tail- > next = list1; if (list2) tail- > next = list2; return head;} determine whether there are rings in the linked list

Give you a head of the head node of the linked list to determine whether there are rings in the linked list.

Returns true if there is a ring in the linked list. Otherwise, return false.

Example 1:

Input: head = [3, 2, 10, 10, 4], pos = 1

Output: true

Explanation: there is a ring in the linked list whose tail is connected to the second node.

Source of topic: force buckle

Idea: we use the method of fast and slow pointers to make the fast pointer take two steps at a time, and the slow pointer take one step at a time. When the linked list has a ring, when slow enters the ring, fast begins to chase slow. Assuming that the distance between fast and slow is N, the distance between fast and slow will be reduced one step each time, that is to say, Nmur1, no, no. The code is implemented as follows:

Bool hasCycle (struct ListNode* head) {struct ListNode* fast = head; struct ListNode* slow = head; while (fast & & fast- > next) {slow = slow- > next; fast = fast- > next- > next; if (slow = = fast) return true;} return false;} to determine the node entered by the circular linked list

Given the header node head of a linked list, returns the first node where the linked list begins to enter the ring. Returns null if the linked list has no loops.

Modification of the linked list is not allowed.

Example 1:

Input: head = [3, 2, 10, 10, 4], pos = 1

Output: returns a linked list node with index 1

Explanation: there is a ring in the linked list whose tail is connected to the second node.

Source of topic: force buckle

Idea: we still use the same fast and slow pointer method as above, but in the back, a pointer starts from the meeting point meet, a pointer starts from the chain header head, and they will meet at the entry point! For illustration, the code reference is as follows:

Bool hasCycle (struct ListNode* head) {struct ListNode* fast = head; struct ListNode* slow = head; while (fast & & fast- > next) {slow = slow- > next; fast = fast- > next- > next; if (slow = = fast) return true;} return false;} these are all the contents of the article "what are the C++ list exercises?" Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.