乐趣区

剑指offer6从尾到头打印链表

题目

输入一个链表的头节点,从尾到头 反过来打印出每个节点的值。

解题思路

一、栈

第一个遍历的节点最后一个输出,而最后一个比遍历到的节点第一个输出(后进先)

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode){ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while(listNode != null){stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.empty()){list.add(stack.pop());
        }
        return list;
    }

二、递归(重点理解)

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ArrayList<Integer> ret = new ArrayList<>();
    if (listNode != null) {ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}
    public static void test2(ListNode node){if(node != null){if(node.next != null){test2(node.next);
            }
        }
        System.out.println(node.val);
        
    }

总结

当链表非常长时,常用递归的方法会导致函数调用的层级很深,从而有可能导致函数调用栈溢出,显然用栈基于循环实现的代码鲁棒性更好。

退出移动版