1.题目

给你单链表的头节点 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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list

2.思路

（1）递归
（2）迭代
思路参考本题官方题解。

3.代码实现（Java）

//思路1————递归
public ListNode reverseList(ListNode head) {
	//递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    /*
    	head->head1->null
		经过 head.next.next = head 之后，得到 head1->head->head1
		经过 head.next = null 之后，得到 head1->head->null
		这样便将 head 与 head1 进行了反转
	*/
    head.next.next = head;
    head.next = null;
    return newHead;
}

//思路2————迭代
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
    	//使用 next 记录当前节点 cur 的下一个节点
        ListNode next = cur.next;
        //将当前节点 cur 的下一个节点指向 prev
        cur.next = prev;
        //cur 和 prev 均向后移动
        prev = cur;
        cur = next;
    }
    return prev;
}