Niuke.com brush questions (1)

重排链表

解法一:暴力

Looking at the sorted sequence we can see that,The first node is followed by the last node,The second node is followed by the second-to-last node,以此类推.So we can find the last node every time and connect it after the current node
我们用一个指针p指向头节点,Each time find the last node of the linked list and join itpbehind the pointed node,然后p再指向下一个节点,直到pStop when the number of subsequent nodes is less than two

class Solution {
    
public:
    void reorderList(ListNode *head) {
    
        ListNode* p = head;
        while(p){
    
            if(p->next && p->next->next){
        // 若p后面至少有两个节点
                ListNode *pre = p->next, *cur = p->next->next;
                while(cur->next){
        // 找到最后一个节点cur, pre指向倒数第二个节点
                    cur = cur->next;
                    pre = pre->next;
                }
                // 将cur接在p后面
                pre->next = nullptr;
                cur->next = p->next;
                p->next = cur;

                p = p->next->next;
            }
            else break;
        }
    }
};

时间复杂度：O(n^2), n为节点数,The time complexity of finding the last one each time is O(n),故总时间复杂度为O(n^2)
空间复杂度：O(1)

解法二:（线性表）

The disadvantage of method 1 is that the linked list cannot access elements through subscripts,Therefore, it takes time to find the last node each time,So we thought that a linear table could be used to store node pointers,Then you can reconnect the linked list
实现细节：We start by putting each node pointer into an array,Then use the double pointer algorithm to take out the two corresponding nodes before and after each time and let the previous node point to the next node,然后用一个指针preRepresents the tail node pointer of the previous section,若pre不为空,There is a linked list in front of the description,让preJust point to the previous node taken out,再令preis the last node taken out,以此类推,最后记得让pre指向空,当然前提是pre自身不为空

class Solution {
    
public:
    void reorderList(ListNode *head) {
    
        vector<ListNode*> vec;    // 创建线性表
        ListNode* cur = head;
        while(cur){
        // Put the node pointer into the linear table
            vec.emplace_back(cur);
            cur = cur->next;
        }
        ListNode* pre = nullptr;
        int i = 0, j = vec.size() - 1;
        while(i <= j){
        // Reconnect the linked list using two-pointer arithmetic
            vec[i]->next = vec[j];
            if(pre) pre->next = vec[i];
            pre = vec[j];
            i++, j--;
        }
        if(pre) pre->next = nullptr;    // The tail node points to a null pointer
    }
};

时间复杂度：O(n), n为链表节点数,The time complexity of the double pointer arithmetic is O(n)
空间复杂度：O(n), Space used by linear tables

解法三:（快慢指针、链表翻转、链表合并）

We can first find the midpoint of the linked list through the fast and slow pointers,Then split the linked list in two,Then flip the second segment of the linked list,Finally, the two linked lists can be crossed and merged into one
This approach involves finding the midpoint of the linked list with the fast and slow pointers,In-place flipping of linked lists and cross-merging of linked lists,综合性很强,The proficiency and basic skills of our pointer use were examined
为了方便理解,I use animations to help you understand the basic implementation principles,Algorithms for in-place flipping of linked lists,I'll demonstrate with a gif at the end

class Solution {
    
public:
    void reorderList(ListNode* head) {
    
        if(!head) return;
        ListNode* mid = GetMid(head);   // 得到链表的中点
        ListNode *p1 = head, *p2 = mid->next;
        mid->next = nullptr;    // 断开链表
        p2 = ReverseList(p2);   // Flip the last linked list
        MergeList(p1, p2);   // Cross-merge two linked lists
    }

    ListNode* GetMid(ListNode* head) {
      // Return to the midpoint of the linked list
        ListNode *slow = head, *fast = head;
        while(fast->next && fast->next->next){
    
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* ReverseList(ListNode* head) {
     // In-place flip of the linked list
        if(!head) return head;
        ListNode *pre = head, *cur = head->next;

        while(cur){
    
            head->next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = head->next;
        }

        return pre;
    }

    void MergeList(ListNode *l1, ListNode *l2) {
       // Cross-merge two linked lists
        ListNode *tmp1, *tmp2;
        while(l1 && l2){
    
            tmp1 = l1->next;
            tmp2 = l2->next;

            l1->next = l2;
            l2->next = tmp1;

            l1 = tmp1;
            l2 = tmp2;
        }
    }
};

时间复杂度：O(n),快慢指针,链表合并,The time complexity of flipping a linked list is bothO(n)的
空间复杂度：O(1)