package normal;

/**
 * @program JavaBooks
 * @description: 206.反转链表
 * @author: mf
 * @create: 2019/11/05 19:36
 */

/*
题目：https://leetcode-cn.com/problems/reverse-linked-list/comments/
类型：链表
难度：easy
 */

public class ReverseList {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        ListNode head = ListNode.setListNode(arr);
        ListNode l = reverseList2(head);
        ListNode.printNode(l);
    }

    /**
     * 递归优点绕，还是用循环好理解一些
     * @param head
     * @return
     */
    private static ListNode reverseList(ListNode head) {
        ListNode pre = null; // 当前节点的前一个节点
        ListNode cur = head; // 当前节点
        while (cur != null) {
            ListNode nextTemp = cur.next; // 先保存当前节点的下一个节点
            cur.next = pre; // 将当前节点的下个节点指向前一个节点pre
            pre = cur; // 将pre往后移动指向当前节点
            cur = nextTemp; // 将当前指点指针往后移动next
        }
        return pre;
    }

    /**
     * 尾递归
     * @param head
     * @return
     */
    private static ListNode reverseList2(ListNode head) {
        return reverse(null, head);
    }
    private static ListNode reverse(ListNode pre, ListNode cur) {
        if (cur == null) return pre;
        ListNode next = cur.next; // 保存当前节点的下个节点的指针
        cur.next = pre;
        return reverse(cur, next);
    }
}