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

package linkedlist;

import common.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import static common.PrintArrayList.printArrayList;

public class 从尾到头打印链表 {

    /**
     * 自想1:
     * 从前到后遍历链表,并用数组存储,最后转换成ArrayList
     * 时间复杂度O(n),空间复杂度O(n)
     */
    public static ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        int length = 0;
        ListNode cur = listNode;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        cur = listNode;
        Integer[] array = new Integer[length];
        for (int i = length - 1; i >= 0 && cur != null; i--) {
            array[i] = cur.val;
            cur = cur.next;
        }
        return new ArrayList<>(Arrays.asList(array));
    }

    /**
     * 讨论区:递归
     * 时间复杂度O(2的n次方),空间复杂度O(1)
     */
    static ArrayList<Integer> arrayList = new ArrayList<>();
    public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        if (listNode != null) {
            printListFromTailToHead2(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(67);
        listNode.next = new ListNode(0);
        listNode.next.next = new ListNode(24);
        listNode.next.next.next = new ListNode(58);
        printArrayList(printListFromTailToHead1(listNode));
        printArrayList(printListFromTailToHead2(listNode));
    }
}

results matching ""

    No results matching ""