题解 | #链表的遍历#

   package 链表;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @Classname JZ6从尾到头打印链表
 * @Description TODO
 * @Date 2022/1/29 10:34
 * @Created by xjl
 */
public class JZ6从尾到头打印链表 {
    public class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    //方法有两种 一种是将数据放入栈中 ，然后在取出
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        if (listNode == null) {
            return null;
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        while (listNode != null) {
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        while (stack.size() != 0) {
            res.add(stack.pop());
        }
        return res;
    }

    //将链表翻转（方法一） 然后在读取链表的数据
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();

        //初始化pre=null curr=listnode
        ListNode pre = null;
        ListNode curr = listNode;

        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = pre;//翻转指针
            pre = curr;//前指后
            curr = temp;//前指后
        }
        while (pre != null) {
            res.add(pre.val);
            pre = pre.next;
        }
        return res;
    }

    //将链表翻转（方法二） 然后在读取链表的数据
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //假设为空的时候
        if (listNode == null) return new ArrayList<Integer>();
        //设置新的节点
        ListNode dumy = new ListNode(-1);
        dumy.next = listNode;
        // 设置新的两个标志位
        ListNode pre = dumy;
        ListNode curr = listNode;

        while (curr.next != null) {
            ListNode future = curr.next;
            curr.next = future.next;
            future.next = dumy.next;
            pre.next = future;
        }
        ListNode result = dumy.next;
        while (result != null) {
            res.add(result.val);
            result = result.next;
        }
        return res;
    }

    public ArrayList<Integer> printListFromTailToHead3cpoy(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (listNode == null) {
            return new ArrayList<Integer>();
        }
        ListNode dumpy = new ListNode(-1);
        dumpy.next = listNode;

        ListNode pre = dumpy;
        ListNode curr = listNode;

        while (curr.next != null) {
            ListNode future = curr.next;
            curr.next = future.next;
            future.next = dumpy.next;
            pre.next = future;
        }
        ListNode ans = dumpy.next;
        while (ans != null) {
            res.add(ans.val);
            ans = ans.next;
        }
        return res;
    }

    //将链表翻转（方法二） 然后在读取链表的数据
    public ArrayList<Integer> printListFromTailToHead4(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        ListNode ans = reverseList(listNode);
        while (ans != null) {
            res.add(ans.val);
            ans = ans.next;
        }
        return res;
    }

    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }

    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}