ผลรวมของโหนดสลับกันใน Linked List ด้วย C++

ในปัญหานี้ กำหนดให้มี Linked List ภารกิจคือหาผลรวมของโหนดสลับกัน (alternate nodes) ของ Linked List

Linked List เป็นโครงสร้างข้อมูลลำดับที่เชื่อมต่อกันผ่านลิงก์

เราจะบวกโหนดที่ตำแหน่ง 0, 2, 4, 6, ...

ตัวอย่าง

Input: 4 → 12 → 10 → 76 → 9 → 26 → 1
Output: 24
คำอธิบาย: โหนดสลับกัน = 4 + 10 + 9 + 1 = 24

วิธีแก้ปัญหา

เยี่ยมชมแต่ละโหนดทีละตัว ใช้ตัวแปร flag สลับค่า true/false เพื่อบอกว่าโหนดปัจจุบันควรนำมาบวกหรือไม่ สามารถทำได้ทั้งแบบ Iterative และ Recursive

วิธี Iterative (วนลูป)

#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

วิธี Recursive (เรียกซ้ำ)

#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