Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of how C++ realizes a group of flipped linked lists per k, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe that after reading this C++ article on how to achieve a group of flipped linked lists per k, we will gain something. Let's take a look.

A set of flipped linked lists per k

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

K is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1-> 2-> 3-> 4-> 5

For k = 2, you should return: 2-> 1-> 4-> 3-> 5

For k = 3, you should return: 3-> 2-> 1-> 4-> 5

Note:

Only constant extra memory is allowed.

You may not alter the values in the list "s nodes, only nodes itself may be changed.

This problem allows us to flip the linked list in groups of each k. In fact, the original linked list is divided into several small segments, and then it is flipped separately. Then a total of two functions must be needed, one for segmentation and the other for flipping. According to the example given in the title, for a given linked list 1-> 2-> 3-> 4-> 5, most of the time when dealing with linked list problems, we will add another dummy node at the beginning. Because the header node may change when flipping the linked list, dummy node is introduced to record the position of the latest header node. After adding dummy node, the linked list becomes-1-> 1-> 2-> 3-> 4-> 5. If k is 3, the goal is to flip 1Magin2 and 3, so you need some pointers. Pre and next point to the position before and after the list to be flipped, and then the position of pre is updated to the following new position after flipping:

-1-> 1-> 2-> 3-> 4-> 5

| | |

Pre cur next

-1-> 3-> 2-> 1-> 4-> 5

| | |

Cur pre next

By analogy, as long as cur walks through k nodes, then next is cur- > next, and you can call the flip function to perform local flipping. Note that the positions of the new cur and pre are different after flipping. After flipping, cur should be updated to pre- > next, and if flipping is not needed, cur will be updated to cur- > next. The code is as follows:

Solution 1:

Class Solution {public: ListNode* reverseKGroup (ListNode* head, int k) {if (! head | | k = = 1) return head; ListNode* dummy = new ListNode (- 1), * pre = dummy, * cur = head; dummy- > next = head; for (int I = 1; cur; + + I) {if (I% k = = 0) {pre = reverseOneGroup (pre, cur- > next) Cur = pre- > next;} else {cur = cur- > next;}} return dummy- > next;} ListNode* reverseOneGroup (ListNode* pre, ListNode* next) {ListNode* last = pre- > next, * cur = last- > next; while (cur! = next) {last- > next = cur- > next Cur- > next = pre- > next; pre- > next = cur; cur = last- > next;} return last;}}

We can also do this in a function, first traversing the entire linked list and counting the length of the linked list, and then if the length is greater than or equal to k, exchange nodes, when KF2, each segment needs to be exchanged only once, when KF3, each segment needs to exchange 2, so I start the cycle from 1, notice that the pre pointer is updated after swapping, and then num minus k until numnext = head; int num = 0 While (cur = cur- > next) + + num; while (num > = k) {cur = pre- > next; for (int I = 1; I

Next; cur- > next = t-> next; t-> next = pre- > next; pre- > next = t;} pre = cur; num-= k;} return dummy- > next;}}

We can also use recursion to record the start position of each segment with head and the next node of the end position with cur, then call the reverse function to flip this segment, and then get a new_head, and the original head becomes the end. At this time, the new node obtained by the recursive call to the next paragraph is followed by the return new_head. See the code as follows:

Solution 3:

Class Solution {public: ListNode* reverseKGroup (ListNode* head, int k) {ListNode* cur = head; for (int I = 0; I

Next;} ListNode* new_head = reverse (head, cur); head- > next = reverseKGroup (cur, k); return new_head;} ListNode* reverse (ListNode* head, ListNode* tail) {ListNode* pre = tail; while (head! = tail) {ListNode* t = head- > next; head- > next = pre; pre = head Head = t;} return pre;}}; this is the end of the article on "how C++ implements a set of flipped linked lists per k". Thank you for reading! I believe you all have a certain understanding of the knowledge of "C++ how to achieve a group of flipped linked lists per k". If you want to learn more knowledge, you are 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.