14931 - Zura's C++ Concert Queue   

Status  |  Limits Submit

Description

Welcome back to this question, again, but in C++ programming language. In this problem, you are tasked to solve this question in C++ and familiarize the C++ syntax.

Katsura (It’s not Zura, it’s Katsura!) and Elizabeth are holding a street rap concert. A massive, single queue of $N$ fans has formed.

However, Katsura made a rule. He decides that the fan at the very front of the line should enter with the fan at the very back of the line. Then, the second person in line should enter with the second-to-last person, and so on.

Given a singly linked list representing the queue $L_0 \to L_1 \to \dots \to L_{n-2} \to L_{n-1}$, you must reorder it into: $L_0 \to L_{n-1} \to L_1 \to L_{n-2} \to L_2 \to L_{n-3} \dots$

There is a restriction: You can only modify the “next” pointer of each node to change the order. If you attempt to modify the node values or return a list containing nodes whose addresses do not belong to the original list, you may receive a wrong answer.

Compiler Option: C++11 or above.

Further Reading

C++ I/O Streams:

Modern C++ Features:

  • nullptr - Type-safe null pointer constant (vs NULL macro)
  • new/delete - Dynamic memory allocation in C++
  • struct declaration - No typedef needed in C++
  • namespaces - Organizing code and preventing naming conflicts (uses street address analogy)

General C++ Reference:

Some differences from C to C++ in this problem:

function.h

-4  typedef struct ListNode_ {
+4  struct ListNode {
-6      struct ListNode_* next;
+6      struct ListNode* next;
-7  } ListNode;
+7  };

main.c -> main.cpp

-2  #include <stdio.h>
+2  #include <iostream>

// static ListNode* newNode(int val)
-8  ListNode* ret = malloc(sizeof(ListNode));
-10 ret->next = NULL;
+6  ListNode* ret = new ListNode();
+9  ret->next = nullptr;
// Similar NULL->nullptr changes at lines: 20->23, 21->24, 25->28, 31->34, 46->49, 50->53, 55->58, 61->64

// int main(void)
+15 // a common practice for better I/O performance
+16 std::ios_base::sync_with_stdio(false);
+17 std::cin.tie(NULL);

// input line 1
-18 scanf("%d", &N);
+21 std::cin >> N;
// Similar scanf->cin change at line 25->28

-49     printf("%d", curr->value);
-51         printf(" ");
+52     std::cout << curr->value;
+54         std::cout << " ";
// Similar printf->cout changes at lines: 55->58

// cleanup
-64     free(tmp);
+67     delete tmp;

Constraints:

  • $1 \le N \le 10^5$ 
  • $-10^9 \le Node.value \le 10^9$

Input

Line 1: $N$, the total number of fans in the queue.
Line 2: $N$ integers representing the values of the fans in order.

Output

Line 1: The values of the fans in the final folded queue, separated by a single space, ending with \n.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14931.cpp

Partial Judge Header

14931.h

Tags




Discuss