206. 反转链表

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

该题在国内的常见算法面试题的出现次数中排第一，递归和非递归这两种方式都一定要掌握。

思路就是交换两个相邻节点的引用关系即可，使用双指针或者递归操作都可以实现，比较简单。注意理解递归的实现，我们返回的是链表的最后一个节点，也就是反转链表的头节点，都是在每次递归返回之后。

/**
 * 206. 反转链表
 * 反转一个单链表。
 * https://leetcode-cn.com/problems/reverse-linked-list/
 * 简单
 */
public class LeetCode206 {

    /**
     * 双指针
     */
    public ListNode reverseList(ListNode head) {
        //前驱
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            //反转head和pre的关系
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 递归
     */
    public ListNode reverseList1(ListNode head) {

        if (head == null || head.next == null) {
            //递归到最深入之后从这里开始返回
            return head;
        }
        ListNode next = reverseList1(head.next);
        //递归方法返回后执行的步骤，反转引用关系
        head.next.next = head;
        head.next = null;
        //返回之前链表的最后一个节点，也就是反转链表的头节点
        return next;
    }

    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;
        }
    }