ในปัญหานี้ เราได้รับรายการที่เชื่อมโยง งานของเราคือพิมพ์ผลรวมของโหนดสำรองของรายการที่เชื่อมโยง
Linked list คือลำดับของโครงสร้างข้อมูลซึ่งเชื่อมต่อเข้าด้วยกันผ่านทางลิงก์
ตอนนี้ขอกลับไปที่ปัญหา ที่นี่ เราจะเพิ่มโหนดสำรองของรายการที่เชื่อมโยง ซึ่งหมายความว่าเราจะเพิ่มโหนดเป็นตำแหน่ง 0, 2, 4, 6, …
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
4 → 12 → 10 → 76 → 9 → 26 → 1
ผลผลิต
24
คำอธิบาย
considering alternate strings − 4 + 10 + 9 + 1 = 24
เพื่อแก้ปัญหานี้ เราจะไปที่แต่ละโหนดทีละโหนดและสำหรับทุกโหนดที่ซ้อนกัน เราจะเพิ่มมูลค่าให้กับผลรวม ในการตรวจสอบโหนด เราจะใช้แฟล็ก
ซึ่งสามารถทำได้โดยใช้การวนซ้ำหรือการเรียกซ้ำ เราจะหารือทั้งสองที่นี่
ตัวอย่าง
แนวทางการทำซ้ำ
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = (*head_ref);
(*head_ref) = newNode;
}
int sumAlternateNodeIt(struct Node* head) {
bool flag = true;
int sum = 0;
while (head != NULL){
if (flag)
sum += head->data;
flag = !flag;
head = head->next;
}
return sum;
}
int main(){
struct Node* head = NULL;
pushNode(&head, 54);
pushNode(&head, 12);
pushNode(&head, 87);
pushNode(&head, 1);
pushNode(&head, 99);
pushNode(&head, 11);
cout<<"The sum of alternate nodes is "<<sumAlternateNodeIt(head);
return 0;
} ผลลัพธ์
The sum of alternate nodes is 24
ตัวอย่าง
วิธีการแบบเรียกซ้ำ
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void sumAlternateNodeRec(struct Node* node, int& sum, bool flag = true){
if (node == NULL)
return;
if (flag == true)
sum += (node->data);
sumAlternateNodeRec(node->next, sum, !flag);
}
int main(){
struct Node* head = NULL;
pushNode(&head, 54);
pushNode(&head, 12);
pushNode(&head, 87);
pushNode(&head, 1);
pushNode(&head, 99);
pushNode(&head, 11);
int sum = 0;
sumAlternateNodeRec(head, sum, true);
cout<<"The sum of alternate nodes is "<<sum;
return 0;
} ผลลัพธ์
The sum of alternate nodes is 24
