C++ 中的链表跳转
c++server side programmingprogramming
假设我们有一个包含正数的单链表节点。我们需要找到相同的链表，其中每个节点的 next 都指向其前方的 val 节点。如果找不到这样的节点，则 next 将为 null。
因此，如果输入为 [2,3,10,5,9]，则输出为 [2, 3, 15, ]
为了解决这个问题，我们将按照以下步骤执行 −
定义一个数组 v
当节点不为 null 时，执行 −
将节点的值插入 v
node := 节点的下一个节点
ret = 值为 0 的新列表节点
temp = ret
i := 0
当 i < v 的大小，执行 −
temp 的下一个节点 := 值为 v[i] 的新列表节点
temp := temp 的下一个节点
i := i + v[i]
返回 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, ]
