解题思路

这题主要就两个办法，迭代和递归

迭代的好处是 O(1) 的空间，毕竟递归需要 O(n) 的栈空间

递归的好处就是不用保存中间变量

迭代

简单来说就是head指针和newList指针一前一后同时向前推进，保存一下head的下一个元素，然后让head指向newList，然后向前推进，这里记得先推进newList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution
{
public:
	ListNode* reverseList(ListNode* head)
	{
		ListNode* newList = nullptr;

		while (head != nullptr)
		{
			auto temp = head->next;
			head->next = newList;
			newList = head;
			head = temp;
		}

		return newList;
	}
};

递归

递归的核心是抓住每次递归的返回值是恒定的，是新链表的头结点。。

先通过递归找到新链表的头结点newList并返回，每次递归做的其实是将还未添加到新链表的最后一个节点添加到新链表中

因为不知道新链表的尾节点，所以采用head->next表示这个尾节点，下面第10行就是将新链表的尾节点指向旧链表的最后一个节点head，然后把新链表的尾节点置空

有一个坑就是处理一下空链表，head需要先判空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution
{
public:
	ListNode* reverseList(ListNode* head)
	{
		if (head == nullptr || head->next == nullptr)
			return head;

		const auto newList = reverseList(head->next);
		head->next->next = head;
		head->next = nullptr;
		return newList;
	}
};