Linked List Jumps in C++

สมมติว่าเรามีโหนด singly linked list ที่มีค่าบวก เราต้องหา linked list เดียวกันนั้นแต่ next ของทุกโหนดชี้ไปยังโหนดที่อยู่ห่างออกไป val โหนด (val nodes ahead) หากไม่พบโหนดดังกล่าว next จะเป็น null

เช่น หากอินพุตคือ [2,3,10,5,9] ผลลัพธ์จะเป็น [2, 3, 15, ]

ขั้นตอนการแก้ปัญหา

• อ่านค่าทั้งหมดจาก linked list ใส่ในอาร์เรย์ v
• สร้าง linked list ใหม่:
  • เริ่มจาก i = 0
  • สร้างโหนดใหม่ด้วยค่า v[i]
  • กระโดด i = i + v[i]
  • ทำซ้ำจน i >= v.size()
• คืนค่า linked list ใหม่

ตัวอย่างโค้ด

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

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) { val = data; next = NULL; }
};

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

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

class Solution {
public:
    ListNode* solve(ListNode* node) {
        vector<int> v;
        while (node) { v.push_back(node->val); node = node->next; }
        ListNode* ret = new ListNode(0);
        ListNode* temp = ret;
        int i = 0;
        while (i < v.size()) {
            temp->next = new ListNode(v[i]);
            temp = temp->next;
            i += v[i];
        }
        return ret->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));
}

อินพุต

{2,2,3,5,9,15,3,4}

เอาต์พุต

[2, 3, 15, ]