Cho một danh sách liên kết đơn, trong đó mỗi nút được mô tả bởi cấu trúc:

struct Node {
    int data;
    Node *next;
};

Danh sách được biểu diễn bởi con trỏ head, trỏ tới nút đầu tiên; danh sách kết thúc khi trường next của nút cuối cùng có giá trị NULL.

Nhiệm vụ của bạn là đảo ngược thứ tự các nút trong danh sách, sao cho:

• Nút đầu tiên trở thành nút cuối cùng,

• Nút cuối cùng trở thành nút đầu tiên,

• Thứ tự tương đối của tất cả các nút bị đảo ngược hoàn toàn.

Sau khi hàm thực hiện xong, con trỏ head phải trỏ tới nút mới ở đầu danh sách (tức là nút vốn là cuối danh sách ban đầu).

Để làm điều này, bạn cần hoàn thiện một hàm trong mã nguồn của giám khảo (xem template ở dưới).

#include "judgement.h"
// Thư viện này chứa sẵn struct Node và các logic kiểm tra

// Được phép khai báo thêm hàm/biến/thư viện ở đây nếu cần

void reverseList(Node *&head) {
    // Hoàn thiện hàm này
}

Thí sinh không được viết hàm main, không được nhập/xuất dữ liệu. Tệp judgement.h sẽ tự động gọi hàm của thí sinh với dữ liệu phù hợp và quản lý việc nhập xuất.

Input

Output

Sample Input 1

6
1 2 2 4 2 6

Sample Output 1

password: 1405759586561168731
6 2 4 2 2 1