Code & Fun

第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;
}

本文首发于Code & Fun