Sword finger offer special assault edition day 8

The finger of the sword Offer II 024. Reverse a linked list

Iterative reverse linked list

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        ListNode *pre = nullptr, *tmp, *ptr = head;
        while(ptr != nullptr) {
    
            tmp = ptr;
            ptr = ptr->next;
            tmp->next = pre;
            pre = tmp;
        }
        return pre;
    }
};

Recursive version （ Slower than iteration ）

class Solution {
    
public:
    void fun(ListNode* now,ListNode* pre,ListNode *(&res)) {
    
        if(now == nullptr) {
    
            res = pre;
            return;
        } else {
    
            fun(now->next,now,res);
            now->next = pre;
        }
    }
    ListNode* reverseList(ListNode* head) {
    
        ListNode *res = nullptr;
        fun(head,nullptr,res);
        return res;
    }
};

---

The finger of the sword Offer II 025. The two numbers in the linked list are added

Similar to high-precision addition , Iterative inversion linked list is used

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        ListNode *pre = nullptr, *tmp, *ptr = head;
        while(ptr != nullptr) {
    
            tmp = ptr;
            ptr = ptr->next;
            tmp->next = pre;
            pre = tmp;
        }
        return pre;
    }

    ListNode* add(ListNode *head1, ListNode *head2) {
    
        ListNode *res = new ListNode(0), *ptr = res;
        int t = 0;
        while(head1 != nullptr || head2 != nullptr || t != 0) {
    
            int sum = t;
            if(head1 != nullptr) {
    
               sum += head1->val;
               head1 = head1->next; 
            }
            if(head2 != nullptr) {
    
                sum += head2->val;
                head2 = head2->next;
            }
            t = sum/10;
            ptr->next = new ListNode(sum%10);
            ptr = ptr->next;
        }
        res = res->next;
        return reverseList(res);
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    
        auto head1 = reverseList(l1);
        auto head2 = reverseList(l2);
        return add(head1,head2);
    }
};

---

The finger of the sword Offer II 026. Rearrange the list

Method 1 、 Linear table storage , Make it possible to randomly access

class Solution {
    
public:
    void reorderList(ListNode* head) {
    
        vector<ListNode*> list;
        ListNode *ptr = head;
        while(ptr != nullptr) {
    
            list.emplace_back(ptr);
            ptr = ptr->next;
        }

        for(auto ptr:list) ptr->next = nullptr;

        int n = list.size();
        for(int i = 0; i < n/2; i++) {
    
            list[i]->next = list[n-i-1];
            if(n-i-1 > i+1) list[n-i-1]->next = list[i+1];
        }
    }
};

Method 2 、 Look for the point in the list + Reverse order of linked list + Merge list （ Knowledge points are more comprehensive ）

Note that the target linked list is the result of combining the left half end of the original linked list and the right half end after inversion .

In this way, our task can be divided into three steps ：

1. Find the midpoint of the original list （ Reference resources 「876. The middle node of a list 」）. We can use the speed pointer to O(N)O(N) Find the middle node of the linked list .
2. Reverse the right half of the list （ Reference resources 「206. Reverse a linked list 」）. We can use the iterative method to reverse the linked list .
3. Merge the two ends of the original linked list . Because the length difference between the two linked lists is no more than 11, Therefore, direct consolidation is sufficient .

class Solution {
    
public:
    void reorderList(ListNode* head) {
    
        if (head == nullptr) {
    
            return;
        }
        ListNode* mid = middleNode(head);
        ListNode* l1 = head;
        ListNode* l2 = mid->next;
        mid->next = nullptr;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    ListNode* middleNode(ListNode* head) {
    
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
    
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head) {
    
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
    
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    void mergeList(ListNode* l1, ListNode* l2) {
    
        ListNode* l1_tmp;
        ListNode* l2_tmp;
        while (l1 != nullptr && l2 != nullptr) {
    
            l1_tmp = l1->next;
            l2_tmp = l2->next;

            l1->next = l2;
            l1 = l1_tmp;

            l2->next = l1;
            l2 = l2_tmp;
        }
    }
};