剑指offer【03】- 从尾到头打印链表(4种实现方法)

题目：从尾到头打印链表

考点：链表

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

法一：ArrayList头插法

 /**

 *    public class ListNode {

 *        int val;

 *        ListNode next = null;

 *

 *        ListNode(int val) {

 *            this.val = val;

 *        }

 *    }

 *

 */

 import java.util.ArrayList;

 public class Solution {

     //ArrayList头插法实现栈功能

     ArrayList<Integer> list = new ArrayList<Integer>();

     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

         while(listNode != null){

            //0 是插入的为值  val 就是吧每次的值取出来插入到0的位置。其他之前的插入的向后顺序移动。

            list.add(0,listNode.val);

             listNode = listNode.next;

         }

         return list;

     }

 }

法二：使用Collections的reverse方法，将list反转

 /**

 *    public class ListNode {

 *        int val;

 *        ListNode next = null;

 *

 *        ListNode(int val) {

 *            this.val = val;

 *        }

 *    }

 *

 */

 import java.util.Collections;

 import java.util.ArrayList;

 public class Solution {

     ArrayList<Integer> list = new ArrayList<Integer>();

     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

         while(listNode != null){

            list.add(listNode.val);

            listNode = listNode.next;

         }

         //使用Collections的reverse方法，直接将list反转

         Collections.reverse(list);

         return list;

     }

 }

法三：递归法

 /**

 *    public class ListNode {

 *        int val;

 *        ListNode next = null;

 *

 *        ListNode(int val) {

 *            this.val = val;

 *        }

 *    }

 *

 */

 import java.util.ArrayList;

 public class Solution {

     //递归实现

     ArrayList<Integer> list = new ArrayList<Integer>();

     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        if(listNode != null){

            this.printListFromTailToHead(listNode.next);

            list.add(listNode.val);

        }

        return list;

     }

 }

递归的点在printListFromTailToHaed(listNode.next)这个节点，那么在最后一次递归方法返回以后，每一层的递归方法都会做一个arrayList.add(lizxstNode.val)这个操作，从最后一次到第一次，逆向的调用了后面的方法。因为之前的递归点已经返回了。

法四：用栈实现

 /**

 *    public class ListNode {

 *        int val;

 *        ListNode next = null;

 *

 *        ListNode(int val) {

 *            this.val = val;

 *        }

 *    }

 *

 */

 import java.util.Collections;

 import java.util.ArrayList;

 import java.util.Stack;

 public class Solution {

     ArrayList<Integer> list = new ArrayList<Integer>();

     Stack<ListNode> stack = new Stack<ListNode>();

     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

         while(listNode != null){

             stack.push(listNode);

             listNode = listNode.next;

         }

         //利用栈后进先出的特点实现翻转

         while(!stack.isEmpty()){

             list.add(stack.pop().val);

         }

         return list;

     }

 }

巴特西

剑指offer【03】- 从尾到头打印链表(4种实现方法)

最新文章

热门文章