LeetCode 每日一题 [11] 反转链表

LeetCode 反转链表 [简单]

反转一个单链表。

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

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

题目分析：

解法1：

先把 node 中的数据取出来存放到集合中，然后再从集合中取出数据，再创建ListNode 放进去。这样使用和额外的空间，肯定不是最优解。面试官肯定会追问的。

解法2：

根据题目的提示，可以使用迭代或者递归，那么使用迭代如何实现呢？
在遍历链表的时候，将当前节点的 next 指向前一个元素，由于节点没有引用上一个节点，因此必须事先存储其前一个元素，我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。第二个指针 cur 指向 head，然后不断遍历 cur。都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

图示

解法3：

递归的两个条件：
终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head
很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。

代码实现

public class LeetCode_11_ReverseLinkedList {

    public static void main(String[] args) {

    }

    //也可以申请额外的空间 但是肯定不是最优解

    public ListNode reverseList01(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //这里的 curr 就是最后一个节点
        ListNode curr = reverseList01(head.next);
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return curr;
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        ListNode next = null;
        while (curr != null) {
            //存储下一个需要移动的指针位置
            next = curr.next;
            //然后将当前节点指向pre
            curr.next = pre;
            //新的头指针向后移动
            pre = curr;
            //头指针向后移动
            curr = next;
        }
        return pre;
    }
}