Leetcode 0143. rearrange linked list

【LetMeFly】143. Rearrange the list

Force button topic link ：https://leetcode.cn/problems/reorder-list/

Given a single chain table L The head node of head , Single chain list L Expressed as ：

L0 → L1 → … → Ln - 1 → Ln

Please rearrange them to ：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You can't just change the value inside the node , It needs to actually exchange nodes .

 

Example 1：

 Input ：head = [1,2,3,4]
 Output ：[1,4,2,3]

Example 2：

 Input ：head = [1,2,3,4,5]
 Output ：[1,5,2,4,3]

 

Tips ：

• The length range of the linked list is [1, 5 * 104]
• 1 <= node.val <= 1000

Method 1 ： Hashtable

Traversing the linked list , Store the linked list nodes in the hash table , The mapping relationship is <[ The first few nodes , node ]>（ In fact, arrays can also be used here , Although the complexity is the same , But the actual cost of arrays is still smaller ）

then , With two Pointers $l$ and $r$, Point to the nodes of the previous processing and the nodes of the subsequent processing respectively

When the current pointer exceeds the rear pointer , Exit loop .

matters needing attention ：

1. use head After traversing the linked list ,head It no longer points to the head node , Remember to head place
2. Remember to put the last node of the linked list next empty

• Time complexity $O(N^2)$
• Spatial complexity $O(N\log N)$

AC Code

C++

class Solution {
    
public:
    void reorderList(ListNode* head) {
    
        unordered_map<int, ListNode*> ma;
        int cnt = 0;
        while (head) {
    
            ma[cnt++] = head;
            head = head->next;
        }
        head = ma[0];  // head place 
        int l = 1, r = cnt - 1;  //  To be specified 
        bool front = false;
        while (l <= r) {
    
            if (front) {
    
                head->next = ma[l++];
                front = false;
            }
            else {
    
                head->next = ma[r--];
                front = true;
            }
            head = head->next;
        }
        head->next = nullptr;  //  Of the last node next empty 
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/126031446