206.反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围是 [0, 5000]
• $-5000\le Node.val\le 5000$

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

解法一(迭代+双指针)

思路分析:

1. 遍历链表节点,对每个节点进行反转; 使用节点p指向新链表的头节点, 节点q则指向每个需要进行反转的节点
2. 在遍历的过程中,反转节点q,即q.next = p, 将每个需要反转的节点都指向新链表头部, 从而实现整个链表的反转

实现代码

class Solution {
    public ListNode reverseList(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode p = null;
		ListNode q = head;
		while (q != null) {
			// 记录下一个反转的节点
			ListNode temp = q.next;
			// 改变节点指向 反转指向前一个节点
			q.next = p;
			// 重新移动p为 新链表头节点
			p = q;
			q = temp;	// 移动q继续反转
		}
		return p;
    }
}

运行结果

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:41.6 MB,击败了7.26% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

解法二(递归)

实现思路

1. 考虑从后往前进行反转,即对于链表[1,2,3,4,5],应该先反转5,让节点5指向4,再接着反转4,让节点4指向3,依次反转;
2. 假设当前节点cur指向节点3, 需要进行反转, 即cur.next.next = cur, 同时避免形成环形链表, 则cur.next = null

实现代码

class Solution {
	public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null)	// head为空 直接返回
			return head;
		ListNode p = reverseList(head.next);
		head.next.next = head;
		head.next = null;
		return p;
	}
}

运行结果

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:41.3 MB,击败了78.38% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$