Đảo ngược danh sách liên kết đơn

[nguyenchiemminhvu (NCMV)]

Ở trung tâm Microsoft trường mình có câu hỏi phỏng vấn như tiêu đề. Mình làm không được nên giờ post lại cho mọi người tham khảo.

#include <iostream>
using namespace std;

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

Node* newElement(int data)  {
    Node* e = new Node;
    e->data = data;
    e->next = NULL;

    return e;
}

void initialize(Node*& n)    {
    n = NULL;
}

void print(Node* n) {
    while(n != NULL)    {
        cout << n->data << " ";
        n = n->next;
    }
}

void addFirst(Node*& n, int data)   {
    Node* e = newElement(data);
    e->next = n;
    n = e;
}

void input(Node*& n) {
    int num_of_element, d;
    cout << "Enter number of element: ";
    cin >> num_of_element;

    for(int i = 0; i < num_of_element; i++) {
        cout << "Enter value: ";
        cin >> d;
        addFirst(n, d);
    }
}

void reverseList(Node*& n)  {
    if(n == NULL)
        return;

    Node *current = NULL;
    Node *previous = NULL;

    while(n != NULL)    {
        current = n;
        n = n->next;
        current->next = previous;
        previous = current;
    }
    n = current;
}

int main()  {

    Node* list;
    initialize(list);
    input(list);
    print(list);

    cout << endl << endl;

    reverseList(list);
    print(list);
    return 0;
}

The result:

[davidteo]

Cảm ơn anh đã chia sẽ. Anh giải thích bằng lời cái hàm > reverseList dùm mình được không? Cảm ơn ạ.

[nguyenchiemminhvu (NCMV)]

Học về danh sách liên kết, cách tốt nhất là dùng hình ảnh chứ ko thể dùng lời được.
Bạn tự vẽ danh sách liên kết ra rồi làm theo những bước trên là cách tốt nhất.

[Bui_Van_Chuong (Bùi Văn Chương)]

Cảm ơn bạn nhiều nhé

[DwarfFungi (abcxyz)]

theo mình nghĩ đảo ngược ds bằng cách chỉ thay đổi giá trị của node chứ k thay đổi liên kết, như thế đơn giản hơn
nhưng lại phức tạp ở khâu tìm ra phần tử đối xứng, vì đây là dslk đơn, và sẽ phải sử dụng vòng lặp nhiều
làm tương tự như đảo ngược 1 mảng

[John_Blacker (Đăng Nguyên Trần Ngọc)]

Mình góp ý xíu là ở phần n = current thì nên đổi lại là n->next=current