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。