Nhảy trên danh sách liên kết trong C++

Cho danh sách liên kết đơn. Tạo danh sách mới: mỗi nút trỏ đến nút cách nó val vị trí. Nếu vượt quá cuối → null.

Ví dụ: [2,2,3,5,9,15,3,4] → nhảy: index 0(val=2)→2(val=3)→5(val=15)→end → [2,3,15].

Thuật toán

• Chuyển linked list sang vector v.
• Duyệt i=0; i

Ví dụ triển khai (C++)

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

struct ListNode {
    int val; ListNode* next;
    ListNode(int d) : val(d), next(nullptr) {}
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* p = head;
        while (p->next) p = p->next;
        p->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode* head) {
    cout << "[";
    while (head) { cout << head->val << ", "; head = head->next; }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* solve(ListNode* node) {
        vector<int> v;
        while (node) { v.push_back(node->val); node = node->next; }
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        for (int i = 0; i < v.size(); i += v[i]) {
            cur->next = new ListNode(v[i]);
            cur = cur->next;
        }
        return dummy->next;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,2,3,5,9,15,3,4};
    ListNode* head = make_list(v);
    print_list(ob.solve(head));
    return 0;
}

Đầu ra

[2, 3, 15, ]