方法一:逆转链表然后输出,设置三个指针pre,cur,next; 然后在next不为null的情况下循环: 1. cur的next指针指向pre元素 2. pre置为cur,cur置为next,next置为下一个元素; 3. 注意最后一次会少添加一个链表,因此需要加上。 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { // 反转链表 ArrayList<Integer> list = new ArrayList<>(); if(listNode == null) return list; // 没有元素 if(listNode.next == null){ list.add(listNode.val); return list; // 只有一个元素 } ListNode pre = listNode,cur=pre.next,next=cur.next; pre.next = null; while(next != null){ cur.next = pre; pre = cur; cur = next; next = next.next; } cur.next = pre; // 少执行一次,应添加 while(cur != null){ list.add(cur.val); cur = cur.next; } return list; }
方法二:
使用递归方法:
1. 递归终止条件为当前list结点的下一个结点为空;
2. 递归寻找当前结点的下一个结点,返回后将当前结点加入list中。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list = new ArrayList<>(); if(listNode == null) return list; dfs(listNode,list); return list; } void dfs(ListNode listNode, ArrayList<Integer> list){ if(listNode.next == null){ list.add(listNode.val); }else { dfs(listNode.next,list); list.add(listNode.val); } }
方法三:先加入栈中,然后弹到list中,该方法比较简单因此略。