LCT0234 回文链表

// 回文链表：将链表的后半部分反转，然后比较前半部分和后半部分是否相等

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(INT_MIN), next(nullptr) {}   // 构造函数
    ListNode(int _val) : val(_val), next(nullptr) {}   // 构造函数
};

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr, *cur = head; // pre指向前一个节点，cur指向当前节点
    while (cur) { // 遍历链表
        ListNode *tmp = cur->next; // 保存当前节点的下一个节点
        cur->next = pre; // 将当前节点的next指针指向前一个节点
        pre = cur; // 将当前节点赋值给前一个节点
        cur = tmp; // 将当前节点指向下一个节点
    }
    return pre; // 返回反转后的链表
}

bool isPalindrome(ListNode* head) {
    ListNode *slow = head, *fast = head; // slow指向链表的中间节点，fast指向链表的尾节点
    while (fast && fast->next) { // 遍历链表
        slow = slow->next; // 将slow指向下一个节点
        fast = fast->next->next; // 将fast指向下下个节点
    }
    if (fast) slow = slow->next; // 如果fast不为空，将slow指向下一个节点
    ListNode *l1 = head, *l2 = reverseList(slow); // l1指向链表的头节点，l2指向链表的中间节点
    while (l2) { // 遍历链表
        if (l1->val != l2->val) return false; // 如果l1的值不等于l2的值，返回false
        l1 = l1->next; // 将l1指向下一个节点
        l2 = l2->next; // 将l2指向下一个节点
    }
    return true; // 返回true
}

ListNode *buildList(vector<int> &nums) { // 建立链表
    ListNode *head = new ListNode(); // 头节点
    ListNode *cur = head; // cur 指向当前节点
    for (int i = 0; i < int(nums.size()); i++) { // 遍历数组
        cur->next = new ListNode(nums[i]); // 将数组元素插入链表
        cur = cur->next; // 将当前节点指向下一个节点
    }
    return head->next; // 返回链表
}

int main() {
    int num;
    vector<int> nums;
    while (cin >> num) {
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    ListNode *head = buildList(nums);
    bool res = isPalindrome(head);
    cout << (res ? "true" : "false") << endl;
    return 0;
}

LCT0206 反转链表

// 反转链表：遍历链表，将当前节点的next指针指向前一个节点，然后将当前节点赋值给前一个节点，最后将当前节点指向下一个节点

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(INT_MIN), next(nullptr) {}   // 构造函数
    ListNode(int _val) : val(_val), next(nullptr) {}   // 构造函数
};

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr, *cur = head; // pre指向前一个节点，cur指向当前节点
    while (cur) { // 遍历链表
        ListNode *tmp = cur->next; // 保存当前节点的下一个节点
        cur->next = pre; // 将当前节点的next指针指向前一个节点
        pre = cur; // 将当前节点赋值给前一个节点
        cur = tmp; // 将当前节点指向下一个节点
    }
    return pre; // 返回反转后的链表
}

ListNode *buildList(vector<int> &nums) { // 建立链表
    ListNode *head = new ListNode(); // 头节点
    ListNode *cur = head; // cur 指向当前节点
    for (int i = 0; i < int(nums.size()); i++) { // 遍历数组
        cur->next = new ListNode(nums[i]); // 将数组元素插入链表
        cur = cur->next; // 将当前节点指向下一个节点
    }
    return head->next; // 返回链表
}

void outputList(ListNode *head) { // 输出链表
    ListNode *cur = head; // cur 指向当前节点
    while (cur) { // 遍历链表   
        cout << cur->val << " "; // 输出当前节点的值
        cur = cur->next; // 将当前节点指向下一个节点
    }
    cout << endl;
}

int main() {
    int num;
    vector<int> nums;
    while (cin >> num) {
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    ListNode *head = buildList(nums);
    ListNode *res = reverseList(head);
    outputList(res);
    return 0;
}

LCT0021 合并两个有序数组

// 合并两个有序链表：遍历两个链表，将较小的节点插入到新链表中

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(-1), next(nullptr) {}   // 构造函数
    ListNode(int _val) : val(_val), next(nullptr) {}   // 构造函数
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode *head = new ListNode(); // 头节点
    ListNode *cur = head; // cur 指向当前节点
    while (l1 && l2) { // 遍历两个链表
        if (l1->val < l2->val) { // 如果l1的值小于l2的值
            cur->next = l1; // 将l1插入到新链表中
            l1 = l1->next; // 将l1指向下一个节点
        } else { // 如果l2的值小于l1的值
            cur->next = l2; // 将l2插入到新链表中
            l2 = l2->next; // 将l2指向下一个节点
        }
        cur = cur->next; // 将当前节点指向下一个节点
    }
    if (l1) cur->next = l1; // 如果l1还有剩余节点，将l1插入到新链表中
    if (l2) cur->next = l2; // 如果l2还有剩余节点，将l2插入到新链表中
    return head->next; // 返回新链表
}

ListNode *buildList(vector<int> &nums) { // 建立链表
    ListNode *head = new ListNode(); // 头节点
    ListNode *cur = head; // cur 指向当前节点
    for (int i = 0; i < int(nums.size()); i++) { // 遍历数组
        cur->next = new ListNode(nums[i]); // 将数组元素插入链表
        cur = cur->next; // 将当前节点指向下一个节点
    }
    return head->next; // 返回链表
}

void outputList(ListNode *head) { // 输出链表
    ListNode *cur = head; // cur 指向当前节点
    while (cur) { // 遍历链表   
        cout << cur->val << " "; // 输出当前节点的值
        cur = cur->next; // 将当前节点指向下一个节点
    }
    cout << endl;
}

int main() {
    int num;
    vector<int> nums1, nums2;
    while (cin >> num) {
        nums1.push_back(num);
        if (cin.get() == '\n') break;
    } 
    while (cin >> num) {
        nums2.push_back(num);
        if (cin.get() == '\n') break;
    } 
    ListNode *l1 = buildList(nums1);
    ListNode *l2 = buildList(nums2);
    ListNode *res = mergeTwoLists(l1, l2);
    outputList(res);
    return 0;
}

LCT0206 反转链表

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(INT_MIN), next(nullptr) {}   // 构造函数
    ListNode(int _val) : val(_val), next(nullptr) {}   // 构造函数
};

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr, *cur = head; // pre指向前一个节点，cur指向当前节点
    while (cur) { // 遍历链表
        ListNode *tmp = cur->next; // 保存当前节点的下一个节点
        cur->next = pre; // 将当前节点的next指针指向前一个节点
        pre = cur; // 将当前节点赋值给前一个节点
        cur = tmp; // 将当前节点指向下一个节点
    }
    return pre; // 返回反转后的链表
}

ListNode *buildList(vector<int> &nums) { // 建立链表
    ListNode *head = new ListNode(); // 头节点
    ListNode *cur = head; // cur 指向当前节点
    for (int i = 0; i < int(nums.size()); i++) { // 遍历数组
        cur->next = new ListNode(nums[i]); // 将数组元素插入链表
        cur = cur->next; // 将当前节点指向下一个节点
    }
    return head->next; // 返回链表
}

void outputList(ListNode *head) { // 输出链表
    ListNode *cur = head; // cur 指向当前节点
    while (cur) { // 遍历链表   
        cout << cur->val << " "; // 输出当前节点的值
        cur = cur->next; // 将当前节点指向下一个节点
    }
    cout << endl;
}

int main() {
    int num;
    vector<int> nums;
    while (cin >> num) {
        nums.push_back(num);
        if (cin.get() == '\n') break;
    } 
    ListNode *head = buildList(nums);
    ListNode *res = reverseList(head);
    outputList(res);
    return 0;
}