6.从尾到头打印链表 6.从尾到头打印链表

题目
【6.从尾到头打印链表】输入链表的第一个节点，从尾到头反过来打印出每个结点的值。

文章图片
思路
1.使用栈 O(N)+O(N)

public ArrayList printListFromTailToHead(ListNode listNode) { Stack stack = new Stack<>(); while (listNode != null) { stack.add(listNode.val); listNode = listNode.next; } ArrayList ret = new ArrayList<>(); while (!stack.isEmpty()) ret.add(stack.pop()); return ret; }

2.使用递归

public ArrayList printListFromTailToHead(ListNode listNode) { ArrayList ret = new ArrayList<>(); if (listNode != null) { ret.addAll(printListFromTailToHead(listNode.next)); ret.add(listNode.val); } return ret; }

3.头插法 O(N)+O(1)

public ArrayList printListFromTailToHead(ListNode listNode) { // 头插法构建逆序链表 ListNode head = new ListNode(-1); while (listNode != null) { ListNode memo = listNode.next; listNode.next = head.next; head.next = listNode; listNode = memo; } // 构建 ArrayList ArrayList ret = new ArrayList<>(); head = head.next; while (head != null) { ret.add(head.val); head = head.next; } return ret; }

4.使用Collections.reserve方法

public ArrayList printListFromTailToHead(ListNode listNode) { ArrayList ret = new ArrayList<>(); while (listNode != null) { ret.add(listNode.val); listNode = listNode.next; } Collections.reverse(ret); return ret; }