206-Reverse Linked List

[難度] easy

[類别] linked list

1.題目描述

反轉連結清單

2.算法描述

（1）第一種算法實作

使用棧作為中間輔助。

首先将連結清單的所有節點push到棧中，然後再從棧中pop出來，即可得到反轉連結清單

代碼實作：

ListNode* reverseList(ListNode* head) {
    stack<ListNode*> mystack;
    //  get reversed list l1
    ListNode* p = head;
    while (p != NULL) {
        mystack.push(p);
        p = p->next;
    }
    if (!mystack.empty()) {
        p = mystack.top();
        mystack.pop();
        head = p;
    }
    while (!mystack.empty()) {
        p->next = mystack.top();
        mystack.pop();
        p = p->next;
    }
    if (p != NULL)
        p->next = NULL;
    return head;
}
           

（2）第二種算法

不另外開辟節點空間，實作連結清單的反轉

ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    ListNode* result = head;
    ListNode* temp = head->next;
    head = temp->next;
    result->next = NULL;
    while (head != NULL) {
        temp->next = result;
        result = temp;
        temp = head;
        head = head->next;
    }
    temp->next = result;
    result = temp;
    return result;
}
           

測試代碼：

void print(ListNode* l1) {
    cout << l1->val;
    l1 = l1->next;
    int count = ;
    while (l1 != NULL) {
        cout << " -> " << l1->val;
        l1 = l1->next;
        count++;
    }
    cout << "   length: " << count << endl;
}
int main() {
    int n1;
    cout << "len1:"
    cin >> n1
    int num;
    ListNode* head = NULL;
    ListNode* l1 = NULL;
    int i = n1;
    while (i--) {
        cin >> num;
        if (i == (n1 -)) {
            head = new ListNode(num);
            l1 = head;
        }
        else {
            head->next = new ListNode(num);
            head = head->next;
        }
    }
    print(l1);
    print(reverseList(l1));
    system("pause");
    return ;
}
           

3.小結

第一種方法比較簡單，直接使用棧作為中間過渡；第二種方法邏輯性強，代碼簡潔且不需要另外開辟記憶體空間。第二種方法的實作比較容易出錯，要特别注意在最開始的時候設定result->next = NULL。