题目描述
Reverse a singly linked list.
例子
例子 1
Input:
1->2->3->4->5->NULLOutput:5->4->3->2->1->NULL
Follow Up
A linked list can be reversed either iteratively or recursively. Could you implement both?
解题思路
如题所述，这道题有两种思路：迭代或者递归，迭代比较简单，递归要注意的点稍微多一点。
迭代法
迭代法主要考虑维护三个节点间的关系：前一个节点（previous）、当前节点（current）、下一节点（next）。对于这三个节点，我们要做的是：
- 存储下一节点，如果不事先做备份，一旦我们更新
current->next，那么下一节点就丢失了 - 更新
current->next使其指向前一节点 - 分别更新
previous和current为current和next，然后重复以上操作
另外注意一些基本例子的操作，代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
method #1: iteratively
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
};
递归法
递归法直观上比较好理解：假定我们有一个递归函数 func，函数逆转给定链表并返回链表尾端节点，那我们要做的是：
- 给定
head，判断如果是空节点或者单节点链表，无须逆转，直接返回head - 否则先逆转后面链表并让其返回的节点指向当前节点，即
func(head->next)->next = head
但是题目要求我们需要返回新链表的头部节点，因此我们需要在递归函数中进行判断，传入一个链表节点指针的引用 new_head（注意是引用，不能是链表节点，否则内部改变链表节点不会影响外部节点），但当前给定的链表是空或者单节点链表时表示已经在进行最后一个节点的逆转，新链表的节点应该是当前节点，对 new_head 进行更新即可。
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return head;
ListNode* new_head = new ListNode();
reverseListRecursivly(head, new_head);
head->next = nullptr;
return new_head;
}
private:
ListNode* reverseListRecursivly(ListNode* head, ListNode*& new_head) {
if (head == nullptr || head->next == nullptr) {
new_head = head;
return head;
}
reverseListRecursivly(head->next, new_head)->next = head;
return head;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址： 206.ReverseLinkedList.cpp
其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions