struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0) : val(x), next(nullptr) {}  // 構(gòu)造函數(shù)支持默認(rèn)值
};

void insertAtHead(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {  // 空鏈表特殊處理
        head = newNode;
        return;
    }
    newNode->next = head;
    head = newNode;
}

void insertAtHeadWithDummy(ListNode* dummy, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = dummy->next;  // 新節(jié)點(diǎn)指向原頭節(jié)點(diǎn)
    dummy->next = newNode;        // 虛擬頭節(jié)點(diǎn)指向新節(jié)點(diǎn)
    // 無需處理空鏈表，dummy->next初始為nullptr，插入后變?yōu)樾鹿?jié)點(diǎn)
}

bool deleteHead(ListNode*& head) {
    if (head == nullptr) return false;  // 空鏈表無節(jié)點(diǎn)可刪
    ListNode* temp = head;
    head = head->next;
    delete temp;
    return true;
}

bool deleteHeadWithDummy(ListNode* dummy) {
    if (dummy->next == nullptr) return false;  // 真實(shí)頭節(jié)點(diǎn)為空
    ListNode* temp = dummy->next;
    dummy->next = temp->next;
    delete temp;
    return true;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);  // 虛擬頭節(jié)點(diǎn)，值0無意義
    ListNode* curr = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    // 連接剩余鏈表
    curr->next = (l1 != nullptr) ? l1 : l2;
    ListNode* result = dummy->next;
    delete dummy;  // 釋放虛擬頭節(jié)點(diǎn)
    return result;
}

ListNode* dummy = new ListNode(-1);  // 值可任意，通常設(shè)為-1或0
dummy->next = head;  // 連接原鏈表

delete dummy;  // 避免內(nèi)存泄漏

std::unique_ptr<ListNode> dummy(new ListNode(0));  // 自動(dòng)管理內(nèi)存

ListNode* findKthFromEnd(ListNode* head, int k) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode *first = dummy, *second = dummy;
    // first先移動(dòng)k+1步（包含dummy）
    for (int i = 1; i <= k + 1; i++) {
        first = first->next;
    }
    // 同時(shí)移動(dòng)first和second
    while (first) {
        first = first->next;
        second = second->next;
    }
    ListNode* result = second->next;
    delete dummy;
    return result;
}

ListNode* reverseList(ListNode* head) {
    ListNode* dummy = new ListNode(0);  // 虛擬頭節(jié)點(diǎn)
    dummy->next = head;
    ListNode* curr = head;
    while (curr && curr->next) {
        // 保存下一個(gè)節(jié)點(diǎn)
        ListNode* nextNode = curr->next;
        // 斷開當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的連接
        curr->next = nextNode->next;
        // 將nextNode插入到虛擬頭節(jié)點(diǎn)之后
        nextNode->next = dummy->next;
        dummy->next = nextNode;
    }
    ListNode* newHead = dummy->next;
    delete dummy;
    return newHead;
}