Reverse Linked List

LeetCode
,

第40天。

今天的题目是Reverse Linked List:

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

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

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

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

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

以及递归的方法:

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