Code & Func

第40天。

Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

简单的想法就是直接用一个栈来完成这种后进先出的操作:

1
ListNode* reverseList1(ListNode* head) {
2
    ListNode ret(0);
3
    ListNode *p = &ret;
4
    stack<ListNode *> st;
5
    while(head!=nullptr) { st.push(head); head = head->next; }
6
    while(!st.empty()) {
7
        p->next = st.top();
8
        st.pop();
9
        p = p->next;
10
    }
11
    p->next = nullptr;
12
    return ret.next;
13
}

但是这种方法效率不高，下面是迭代的方法：

1
ListNode* reverseList(ListNode* head) {
2
    ListNode *pre = nullptr;
3
    ListNode *cur = head;
4
    while(cur != nullptr) {
5
        ListNode *t = cur->next;
6
        cur->next = pre;
7
        pre = cur;
8
        cur = t;
9
    }
10
    return pre;
11
}

以及递归的方法:

1
ListNode *reverseList(ListNode *head) {
2
    if (head==nullptr || head->next == nullptr) return head;
3
    ListNode *ret = reverseList(head->next);
4
    head->next->next = head;
5
    head->next = nullptr;
6
    return ret;
7
}