1 题目地址

206. 反转链表 - 力扣（LeetCode）206. 反转链表 - 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1：[https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg]输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]示例 2：[https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg]输入：head = [1,2]输出：[2,1]示例 3：输入：head = []输出：[] 提示： * 链表中节点的数目范围是 [0, 5000] * -5000 <= Node.val <= 5000 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？https://leetcode.cn/problems/reverse-linked-list/description/

2 题目说明

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

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

3 解题思路

方式一：定义一个新的链表实现链表反转，这种方式对内存极不友好，对内存会产生很大的浪费
方式二：只需要改变链表next指针的方向，直接将链表反转，而不用重新定义一个新的链表。

之前的链表头节点是12，反转后是15，这里并没有添加或者删除元素，仅仅是改变了next的指针方向。

双指针法：

步骤：
1、定义curr指针指向头节点
2、定义pre指针初始化为NULL
3、定义temp=curr.next(中间变量存储curr，防止因为curr的指向变化导致原指向被覆盖的情况)
4、反转：curr.next=pre
5、pre、curr指针向后移动一格
6、重复3 4 5，直到curr指向NULL结束

递归法：

        用递归的方式实现双指针法，核心逻辑和流程是一样的，

1、递归的出口还是curr节点为空则返回pre
2、递归的内容，curr.next=pre
3、移动pre curr，再次反转处理(重复的逻辑处理逻辑)

4 代码编写

4.1 双指针法

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr!=null) {
            // 指向下一个节点，如果指向curr，会因为curr重新赋值导致异常
            ListNode temp = curr.next;
            curr.next = pre;

            // 想后移动
            pre = curr;
            curr = temp;
        }
        return pre;
    }
}

 

4.2 递归法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    public ListNode reverse(ListNode pre, ListNode head) {
        if (head==null) {
            return pre;
        }

        ListNode temp = head.next;
        head.next = pre;

        pre = head;
        head = temp;
        return reverse(pre, head);
    }
}