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

This article mainly introduces C++ how to achieve chain list reordering related knowledge, the content is detailed and easy to understand, simple and fast operation, has a certain reference value, I believe that you will have something to gain after reading this C++ article on how to achieve chain list reordering. let's take a look.

Chain list reordering

Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln

Reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

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

Example 1:

Given 1-> 2-> 3-> 4, reorder it to 1-> 4-> 2-> 3.

Example 2:

Given 1-> 2-> 3-> 4-> 5, reorder it to 1-> 5-> 2-> 4-> 3.

This chain table reordering problem can be divided into the following three minor problems:

1. Use the fast and slow pointer to find the midpoint of the linked list and disconnect the list from the midpoint to form two separate linked lists.

two。 Flip the second chain.

3. Insert the elements of the second linked list into the first linked list at intervals.

Solution 1:

Class Solution {public: void reorderList (ListNode * head) {if (! head | |! head- > next | |! head- > next- > next) return; ListNode * fast = head, * slow = head; while (fast- > next & & fast- > next- > next) {slow = slow- > next; fast = fast- > next- > next;} ListNode * mid = slow- > next; slow- > next = NULL ListNode * last = mid, * pre = NULL; while (last) {ListNode * next = last- > next; last- > next = pre; pre = last; last = next;} while (head & & pre) {ListNode * next = head- > next; head- > next = pre; pre = pre- > next Head- > next- > next = next; head = next;}

We try to see if we can write it more succinctly, the second step above is to flip the second half of the linked list, then we can actually take advantage of the last-in-first-out feature of the stack, if we press all the nodes into the stack in order, then you can reverse the order when you go out of the stack, which is actually equivalent to flipping the linked list. Because we only need to flip the second half of the linked list, then we have to control the number of stack nodes, fortunately, the stack can directly get the number of nodes, we minus 1 divided by 2, we want to get the number of stack nodes. Then what we need to do is to insert each node out of the stack into the correct position, so as to meet the order required in the question. The operation of inserting nodes into the linked list is more common, so there is no more explanation here. Finally, remember to disconnect the nodes behind the elements at the top of the stack, for example, for 1-> 2-> 3-> 4, there is only one node 4 at the top of the stack, and then add the original list to 1-> 4-> 2-> 3-> (4). Because node 3 is connected to node 4 in the original linked list, although we take out node 4 and insert node 4 between node 1 and 2, the pointer behind node 3 is still connected to node 4, so we have to disconnect the connection so that the ring does not appear. Because node 3 is at the top of the stack, we can directly disconnect the top node of the stack. See the code below:

Solution 2:

Class Solution {public: void reorderList (ListNode * head) {if (! head | |! head- > next | |! head- > next- > next) return; stack st; ListNode * cur = head; while (cur) {st.push (cur); cur = cur- > next;} int cnt = ((int) st.size ()-1) / 2; cur = head While (cnt-- > 0) {auto t = st.top (); st.pop (); ListNode * next = cur- > next; cur- > next = t; t-> next = next; cur = next;} st.top ()-> next = NULL;}} This is the end of the article on "how to reorder the chain list on C++". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to achieve chain table reordering on C++". 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.