Output for specific test case in linked list deletes two numbers randomly

Viewed 29

I'm working on a linked list program that takes an input for the data of each node like:

Sample Input: 2 18 24 3 5 7 9 6 12

Then it takes each group of even numbers like "2, 18, and 24" and reverses it to be "24, 18, and 2."

It seems to work on a larger scale according to these unit tests, but this particular one outputs:

2 3 5 7 9 12 6

Instead of:

24 18 2 3 5 7 9 12 6

So it just seems to delete the 24 and the 18 and I'm not sure why. Thanks in advance.

Here's my code:

#include <iostream>
using namespace std;

struct node {
  int data;
  node *next;
  node *prev;
  node *curr;
};

class linked_list {

private:
  node *head,*tail;

public:

  linked_list() {
    head = NULL;
    tail = NULL;
  }

  void add_node(int n) {
    node *tmp = new node;
    tmp->data = n;
    tmp->next = NULL;

    if(head == NULL) {
      head = tmp;
      tail = tmp;
    }
    else {
      tail->next = tmp;
      tmp->prev = tail;
      tail = tail->next;
    }
  }

  node* getHead() {
    return head;
  }

  void print_List() {
    node *tmp;
    tmp = head;
    while (tmp != NULL) {
      cout << tmp->data << " ";
      tmp = tmp->next;
    }
  }

  node* reverse_Groups(node* head, node* prev) {

    if (head == NULL) {
      return NULL;
    }

    node *tmp;
    node *curr;
    curr = head;

    while (curr != NULL && curr->data % 2 == 0) {
      tmp = curr-> next;
      curr->next = prev;
      prev = curr;
      curr = tmp;
    }

    if (curr != head) {
      head->next = curr;
      curr = reverse_Groups(curr, NULL);
      return prev;
    }
    else {
      head->next = reverse_Groups(head->next, head);
      return head;
    }
  } 
};

int main() {
  linked_list a;
  int numNodes, i, tempNode;
  
  cin >> numNodes;
  
  for (i = 0; i < numNodes; ++i) {
    cin >> tempNode;
    a.add_node(tempNode);
  }
  
  //a.print_List();
  a.reverse_Groups(a.getHead(), NULL);
  a.print_List();

  
  return 0;
}
1 Answers

So I figured out it was a minor oversight on my end. The code within reverse_Groups returns head when it's done. I was printing the list from the temp variable rather than the head, so it wasn't printing the first two numbers. Once I figured this out, I added a getHead function that returns the correct head after the reverse function finishes.

I just changed the print function to have a head parameter and supply the correct head using the getHead function so that it prints from the right starting point.

Related