チェーンテーブル逆シーケンス出力の3つのアルゴリズム

チェーンテーブルを入力し、チェーンテーブルの各ノードの値を末尾から印刷します.全部で3つの方法があります.1つ目の方法は私自身の方法で、他の2つは他の人を参考にして、それぞれスタックを利用して再帰します.

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */

1つ目の方法:

public static ArrayList<Integer> printTailToHead1(ListNode listNode)
    {
        //               
        int num = 1;
        ArrayList<Integer> a = new ArrayList<Integer>();
        //            
        while(listNode != null)
        {
            a.add(listNode.val);
            listNode = listNode.next;
            num ++;
        }
        //    ，         
        for(int i = a.size() - 1,j = 0;i > j;j ++,i --)
        {
            int temp = a.get(i);
            a.set(i, a.get(j));
            a.set(j, temp);
        }
        return a;
    }

方法2:スタックの利用

public static ArrayList<Integer> printTailToHead2(ListNode listNode)
    {
        //      ，     java.util.stack
        Stack<Integer> stack = new Stack<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        //         
        while(listNode != null)
        {
            stack.add(listNode.val);
            //     
            listNode = listNode.next;
        }
        //        ，    list
        while(!stack.isEmpty())
        {
            list.add(stack.pop());
        }
        return list;
    }

方法3:再帰

public static ArrayList<Integer> printTailToHead2(ListNode listNode)
    {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //        
        if(listNode != null)
        {
            //           ，              
            if(listNode.next != null)
            {
                list = printTailToHead2(listNode.next);
            }
            //                  
            list.add(listNode.val);
        }
        return list;
    }