« Delete alternate nodes in a LinkedList

Delete Alternate Nodes

Given a Singly Linked List of integers, delete all the alternate nodes in the list.

Example:

List: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null

Alternate nodes will be: 20, 40, and 60.

Hence after deleting, the list will be:

Output: 10 -> 30 -> 50 -> null

Note :

The head of the list will remain the same.

Input format :

The first and the only line of input will contain the elements of the Singly Linked List separated by a single space and terminated by -1.

Output Format :

The only line of output will contain the updated list elements.

Input Constraints:

1 <= N <= 10 ^ 6.

Where N is the size of the Singly Linked List

Time Limit: 1 sec

Sample Input 1:

1 2 3 4 5 -1

Sample Output 1:

1 3 5

Explanation of Sample Input 1:

2, 4 are alternate nodes so we need to delete them

Sample Input 2:

10 20 30 40 50 60 70 -1

Sample Output 2:

10 30 50 70

Copy
1#include <iostream>
2using namespace std;
3
4class Node {
5public:
6    int data;
7    Node * next;
8    Node(int data){
9        this -> data = data;
10        this -> next = NULL;
11    }
12
13    ~Node() {
14        if(next) {
15            delete next;
16        }
17    }
18};
19
20void deleteAlternateNodes(Node *head) {
21    Node *temp = head;
22    while(temp != NULL && temp->next != NULL){
23        Node *next = temp->next->next;
24        temp->next = next;
25        temp = temp->next;
26    }
27}
28
29Node* takeinput() {
30    int data;
31    cin >> data;
32    Node *head = NULL, *tail = NULL;
33    while(data != -1){
34        Node *newNode = new Node(data);
35        if(head == NULL) {
36            head = newNode;
37            tail = newNode;
38        }
39        else{
40            tail -> next = newNode;
41            tail = newNode;
42        }
43        cin >> data;
44    }
45    return head;
46}
47
48void print(Node *head) {
49    Node *temp = head;
50    while(temp != NULL) {
51        cout << temp -> data << " ";
52        temp = temp -> next;
53    }
54    cout << endl;
55}
56
57int main() {
58    Node *head = takeinput();
59    deleteAlternateNodes(head);
60    print(head);
61    delete head;
62    return 0;
63}