Danh sách được Liên kết Nhảy trong C ++

Giả sử chúng ta có một nút danh sách liên kết đơn chứa các số dương. Chúng ta phải tìm cùng một danh sách liên kết mà ở đó mọi nút tiếp theo đều trỏ đến các nút val của nút phía trước. Nếu chúng ta không thể tìm thấy nút như vậy, nút tiếp theo sẽ là null.

Vì vậy, nếu đầu vào là [2,3,10,5,9], thì đầu ra sẽ là [2, 3, 15,]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng v

• trong khi nút không rỗng, do -

  • chèn giá trị của nút vào v

  • node:=next of node

• ret =nút danh sách mới với giá trị 0

• temp =ret

• i:=0

• trong khi tôi

  • next of temp:=nút danh sách mới với giá trị v [i]

  • temp:=next of temp

  • i:=i + v [i]

• trở lại tiếp theo của ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,2,3,5,9,15,3,4};
   ListNode *head = make_list(v);
   print_list(ob.solve(head));
}

Đầu vào

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

Đầu ra

[2, 3, 15, ]