三分学 七分练

leetcode 21

#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
   public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
        if (list1 == nullptr || list2 == nullptr) {
            return list1 == nullptr ? list2 : list1;
        }
        // tail insert
        ListNode header;
        ListNode *tail = &header;
        ListNode *tmp;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val > list2->val) {
                tmp = list1;
                list1 = list2;
                list2 = tmp;
            }
            tail->next = list1;
            while (list1 != nullptr && list1->val <= list2->val) {
                tmp = list1;
                list1 = list1->next;
            }
            tail = tmp;
        }
        if (list1 == nullptr) {
            tmp->next = list2;
        }
        return header.next;
    }
};
int main() {
    ListNode list1_4(4);
    ListNode list1_2(2, &list1_4);
    ListNode list1_1(1, &list1_2);
    ListNode list2_4(4);
    ListNode list2_3(3, &list2_4);
    ListNode list2_1(1, &list2_3);
    Solution sol;
    ListNode *result = sol.mergeTwoLists(&list1_1, &list2_1);
}

leetcode 234

class Solution {
   public:
    bool isPalindrome(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        //  1
        //  ^
        //  1 2 3 4 5 6 7
        //        ^     ^
        //  1 2 3 4 5 6 7 8
        //        ^     ^
        ListNode *tmp;
        while ((tmp = fast->next) != nullptr && (fast = tmp->next) != nullptr) {
            slow = slow->next;
        }
        //  1 2 3 4   5 6 7
        //        ^     ^
        fast = slow->next;
        slow->next = nullptr;
        while (fast != nullptr) {
            tmp = fast->next;

            fast->next = slow->next;
            slow->next = fast;

            fast = tmp;
        }
        fast = slow->next;
        while (fast != nullptr) {
            if (fast->val != head->val) return false;
            fast = fast->next;
            head = head->next;
        }
        return true;
    }
};
int main() {
    Solution sol;
    ListNode right1(1);
    ListNode right2(2, &right1);
    ListNode left2(2, &right2);
    ListNode left1(1, &left2);
    cout << sol.isPalindrome(&left1);
}

leetcode 876

class Solution {
   public:
    ListNode *middleNode(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        //  1 2 3 4 5
        //      ^   ^
        //  1 2 3 4 5 6
        //      ^   ^
        while ((head = fast->next) != nullptr && (fast = head->next) != nullptr) {
            slow = slow->next;
        }
        return head == nullptr ? slow : slow->next;
    }
};

leetcode 19

class Solution {
   public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *ahead = head;
        while (n != 0) {
            ahead = ahead->next;
            --n;
        }
        ListNode *tmp = head;
        if (ahead == nullptr) {
            tmp = head->next;
            head->next = nullptr;
            return tmp;
        }
        //  1 2
        //  ^   ^
        //   1 2 3 4 5 6 7
        //   ^ ^   ^
        //             ^   ^

        ListNode *delBefore = head;
        ListNode *del = head->next;
        ahead = ahead->next;
        while (ahead != nullptr) {
            delBefore = del;
            del = del->next;
            ahead = ahead->next;
        }
        delBefore->next = del->next;
        del->next = nullptr;
        return head;
    }
};