代码随想录二刷 ｜ 链表 ｜ 翻转链表

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路 & 代码实现

双指针法

只需要改变链表的 next 指针的指向，直接将链表翻转，而不用重新定义一个链表。

首先定义一个 cur 指针指向头节点，在定义一个 pre 指针初始化为 null

随后将cur->next节点用 tmp指针保存一下，随后将cur -> next指向 pre ，这样就完成了第一个节点的翻转。

接下来进入循环继续移动 pre 和 cur 指针，最后 cur指针指向 null ，循环结束，链表翻转完成，return pre指针， pre指针就指向了头节点。

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		ListNode* tmp;
		ListNode* cur = head;
		ListNode* pre = NULL;
		while (cur) {
			tmp = cur -> next;
			cur -> next = pre;
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
};

时间复杂度：O(n)
空间复杂度：O(1)

递归法

class Solution {
public:
	ListNode* reverse(ListNode* pre, ListNode* cur) {
		if (cur == NULL) return pre;
		ListNode* tmp = cur -> next;
		cur -> next = pre;
		// 递归写法实际上也是做了这两步
		// pre = cur;
		// cur = tmp;
		return reverse(cur, tmp);
	}
	ListNode* reverseList(LKistNode* head) {
		return reverse(NULL, head);
	}
};