รายการที่เชื่อมโยงข้ามใน C ++

สมมติว่าเรามีโหนดรายการที่เชื่อมโยงโดยลำพังที่มีจำนวนบวก เราต้องหาลิงค์ลิสต์แบบเดียวกัน โดยที่ทุก ๆ โหนดจะชี้ไปที่ node val nodes ข้างหน้า หากเราไม่พบโหนดดังกล่าว โหนดถัดไปจะเป็นโมฆะ

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ v

• ในขณะที่โหนดไม่เป็นโมฆะให้ทำ -

  • แทรกค่าของโหนดลงใน v

  • โหนด :=ถัดไปของโหนด

• ret =โหนดรายการใหม่ที่มีค่า 0

• อุณหภูมิ =ret

• ผม :=0

• ในขณะที่ฉัน <ขนาดของ v ทำ -

  • ถัดไปของ temp :=รายการโหนดใหม่ที่มีค่า v[i]

  • temp :=ถัดไปของอุณหภูมิ

  • ผม :=ผม + วี[ผม]

• กลับมาถัดไปของ ret

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

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

ผลลัพธ์

[2, 3, 15, ]