美文网首页
[剑指offer] 链表01:从尾到头打印链表

[剑指offer] 链表01:从尾到头打印链表

作者: 请收下章鱼君的膝盖 | 来源:发表于2018-12-04 22:29 被阅读8次

    题目描述

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

    解题思路(Java)

    1)利用栈来实现;
    2)用Collections集合类;
    3)利用三个指针把链表反转,关键是 r 指针保存断开的节点;
    4)借助递归实现(递归的本质还是使用了堆栈结构)

    • 统一定义:
    /**
     * 定义一个ListNode类
     * @author 章鱼宝宝
     *
     */    
    class ListNode{
      int val; //数据域
      ListNode next = null; //指针域 
    
      public ListNode(int val) {
        this.val=val;
      }
    }
    
    • 1)利用栈来实现
    public class Demo01 {
      public static  ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(listNode!=null) {
            stack.push(listNode.val);
            listNode=listNode.next;     
        }
        while(!stack.isEmpty()) {
            list.add(stack.pop());
        }   
        return list;
      }
    }
    
    • 2)用Collections集合类
    public class Demo01 {
      public static  ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         ArrayList<Integer> list = new ArrayList<Integer>();
         while(listNode!=null) {
            list.add(listNode.val);
            listNode=listNode.next;
         }
         Collections.reverse(list);     
         return list;
      } 
    }
    
    • 3)利用三个指针把链表反转,关键是 r 指针保存断开的节点
    public class Demo01 {
      public static  ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null)
            return new ArrayList<Integer>();
        ListNode head = listNode;
        ListNode cur = listNode.next;
        while(cur!= null){
            ListNode temp = cur.next;
            cur.next = head;
            head = cur;
            cur = temp;
        }
        //此时listNode的next还指向第二个node,所以要让listNode.next=null,防止循环
        listNode.next = null;
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(head !=null){
            res.add(head.val);
            head = head.next;
        }
        return res;
      }
    }
    
    • 4)借助递归实现(递归的本质还是使用了堆栈结构)
    public class Demo01 {
      public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        ListNode pNode=listNode;
        if(pNode!=null){
            if(pNode.next!=null){
                list=printListFromTailToHead(pNode.next);
            }
            list.add(pNode.val);
        }
    
        return list;
      }
    }
    
    • 测试主方法
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode.next = listNode2;
        System.out.println(printListFromTailToHead(listNode));
      }
    

    相关文章

      网友评论

          本文标题:[剑指offer] 链表01:从尾到头打印链表

          本文链接:https://www.haomeiwen.com/subject/yoqbcqtx.html