每天一道编程题6--链表

74 阅读 0 评论 49 点赞

我是靠谱客的博主精明纸飞机，最近开发中收集的这篇文章主要介绍每天一道编程题6--链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题目描述

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

2.首先这个链表的节点已经给出

public class ListNode {
    int val;
    ListNode next = null;

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

第一种方法比较直接，传进来的是一个链表，返回的一个链表倒序的值，那么可以先顺序添加到一个集合里面，然后再倒序遍历添加到另一个集合里面返回即可

public class TestLink {
    /**
     * 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
     */
    public static void main(String[] args) {
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(4);
        ListNode listNode5=new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        TestLink testLink = new TestLink();
        ArrayList<Integer> list = testLink.printListFromTailToHead(listNode1);
        System.out.println(list);
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        ListNode temp = listNode;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            resultList.add(list.get(i));
        }

        return resultList;
    }
}

第二种方法可以采用递归的算法：首先递归算法要有两个要求，第一要有结束条件，没有结束条件就是死循环，第二，外层的值依赖于内层值得计算，对于这个题而言，最终返回的的是一个集合，而我们内层和外层计算结果都是值，所以只需要每层计算结束后将结果值添加到集合中即可。



public class TestLink {
    /**
     * 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
     */
    public static void main(String[] args) {
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(4);
        ListNode listNode5=new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        TestLink testLink = new TestLink();
        ArrayList<Integer> list = testLink.printListFromTailToHead(listNode1);
        System.out.println(list);
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode==null){
            return list;
        }
        if (listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}