Sword finger offer special shock edition day 9

The finger of the sword Offer II 027. Palindrome list

$O(n)$ Time complexity and $O(1)$ Spatial complexity

class Solution {
    
public:
    ListNode* mid_node(ListNode* head) {
    
        ListNode *slow = head, *fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr) {
    
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverse_list(ListNode *head){
    
        ListNode *pre = nullptr, *cur = head, *tmp;
        while(cur != nullptr) {
    
            tmp = cur;
            cur = cur->next;
            tmp->next = pre;
            pre = tmp;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
    
        if(head == nullptr) return true;
        auto i = head, j = mid_node(head)->next;
        j = reverse_list(j);
        while(i != nullptr && j != nullptr) {
    
            if(i->val != j->val) return false;
            i = i->next, j = j->next;
        }
        return true;
    }
};

---

The finger of the sword Offer II 028. Flatten multi-level bidirectional linked list

1. First recursively flatten the linked list （ Just make sure next The pointer ）
2. Then iterate again to empty child The pointer , Reassign prev The pointer

class Solution {
    
public:
    Node* last_ptr(Node *head) {
    
        Node *cur = head, *pre = head->prev;
        while(cur != nullptr) {
    
            if(cur->child != nullptr) {
    
                auto tmp = cur->next;
                cur->next = cur->child;
                auto child_last = last_ptr(cur->child);
                child_last->next = tmp;
                pre = child_last;
                cur = tmp;
            } else {
    
                pre = cur;
                cur = cur->next;
            }
        }
        return pre;
    }
    Node* flatten(Node* head) {
    
        if(head == nullptr) return nullptr;
        last_ptr(head);
        auto cur = head , prev = head->prev;
        while(cur != nullptr) {
    
            cur->child = nullptr;
            cur->prev = prev;
            prev = cur;
            cur = cur -> next;
        }
        return head;
    }
};

---

The finger of the sword Offer II 029. Sorted circular linked list
simulation , Distinguish between various situations

class Solution {
    
public:
    Node* insert(Node* head, int insertVal) {
    
        if(head == nullptr) {
    
            head = new Node(insertVal);
            head->next = head;
        } else {
    
            if(head == head->next) {
     // Single point loop 
                head->next = new Node(insertVal,head);
            } else {
    
                Node *cur = head->next, *pre = head;
                while(cur != head) {
    
									// Between maximum and minimum ,insertValue It can be inserted if it is the maximum or minimum 
                    if(cur->val < pre->val && (insertVal >= pre->val || insertVal <= cur->val)) {
    
                        pre->next = new Node(insertVal, cur);
                        break;
                    }
									// Values in cur and pre Can be inserted between 
                    if(insertVal >= pre->val && insertVal <= cur->val) {
    
                        pre->next = new Node(insertVal, cur);
                        break;
                    }
                    pre = cur;
                    cur = cur->next;
                }
							// When the elements in the list are equal 
                if(cur == head) {
     
                    pre->next = new Node(insertVal, cur);
                }
            }
        }
        return head;
    }
};