从尾到头打印链表

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList

解题思路

本题要求按照链表的逆序进行输出，要想做到逆序，有三种方法

注：个人认为第二种可能更符合题意

1、将链表每个节点的值输入到ArrayList中，然后将ArrayList逆序

• 1.1 ArrayList逆序方法：头尾交换，以中间为间隔，第一位和最后一位交换，第二位和倒数第二位交换，以此类推

  
  
  数组逆序.png

2、将链表逆序，然后将每个节点的值输入到ArrayList中

• 2.1 链表逆序方法：就地反转
  ● 最开始有一个如图的链表，让链表头listNode指向NULL
  ● 在每次遍历中，记录下listNode.next（temp）以及temp.next
  ● 修改链表的指向，即temp.next = listNode
  ● 将listNode、temp及temp.next依此向后移动
  ● 最终listNode即为逆序后的链表

  
  
  链表反转.png

3、递归

凡是和逆序相关的都可想到递归

代码一

public class Solution {
    // arraylist逆序
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (listNode == null) {
            return arrayList;
        }
        while (listNode != null) {
            arrayList.add(listNode.val);
            listNode = listNode.next;
        }
        for(int i = 0,j = arrayList.size() - 1; i<arrayList.size()/2; i++,j--) {
            int temp = arrayList.get(i);
            arrayList.set(i, arrayList.get(j));
            arrayList.set(j, temp);
        }
        return arrayList;
    }
}

代码二

public class Solution {
    // 链表逆序
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (listNode == null) {
            return arrayList;
        }
        ListNode temp = listNode.next;
        listNode.next = null;
        while (temp != null) {
            ListNode listNodeNext = temp.next;
            temp.next = listNode;
            listNode = temp;
            temp = listNodeNext;
        }
        while (listNode != null) {
            arrayList.add(listNode.val);
            listNode = listNode.next;
        }
        return arrayList;
    }
}

代码三

public class Solution {
    // 递归
    ArrayList<Integer> arrayList = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode != null) {
            printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}