每日两题 / 234. 回文链表 && 21. 合并两个有序链表（LeetCode热题100）

234. 回文链表 - 力扣（LeetCode）

先创建一个指针指向第一个节点
dfs到最后一个节点，开始与第一个节点进行比较

class Solution {
public:
    ListNode *t;
    bool dfs(ListNode *cur)
    {
        if (cur == nullptr)
                return true;
            if (!dfs(cur->next)) return false;
            if (t->val != cur->val) return false;
            t = t->next;
            return true;            
    }
    bool isPalindrome(ListNode* head) {
        t = head;
        return dfs(head);
    }
};

---

21. 合并两个有序链表 - 力扣（LeetCode）

保证list1的首元素小于list2首元素，然后将list2插入到list1
cur1指向list1第二个节点，pre1指向第一个，cur2指向list2第一个节点
若最后cur2不为空，说明list2的节点还没有插入到list1，插入剩余节点即可

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        if (list1->val > list2->val) swap(list1, list2);
        ListNode *pre1 = list1, *cur1 = nullptr;
        if (pre1) cur1 = pre1->next;
        ListNode *cur2 = list2;
        while (cur1)
        {
            while (cur2 && cur2->val <= cur1->val)
            {
                ListNode *next2 = cur2->next;
                pre1->next = cur2;
                pre1 = cur2;
                cur2->next = cur1;
                cur2 = next2;
            }
            cout << cur1->val << '\n';
            ListNode *next1 = cur1->next;
            pre1 = cur1, cur1 = next1;
        }
        while (cur2)
        {
            pre1->next = cur2;
            pre1 = cur2;
            cur2 = cur2->next;
        }
        return list1;
    }
};