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

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个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));
  }