이 문제에서는 연결 목록이 제공됩니다. 우리의 임무는 연결 리스트의 대체 노드의 합을 출력하는 것입니다.
연결된 목록은 링크를 통해 함께 연결된 일련의 데이터 구조입니다.
이제 문제로 돌아가 보겠습니다. 여기에 연결 목록의 대체 노드를 추가합니다. 이것은 우리가 위치 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