Today’s topic comes from the finger Offer series 06 on LeetCode. Print the linked list from end to end.

Title link: leetcode-cn.com/problems/co…

1. Title Description

Enter the head node of a linked list and return the value of each node from end to end (as an array).

Example 1:

Input: head = [1,3,2] output: [2,3,1]Copy the code

Limitations:

  • 0 <= List length <= 10000

Second, the topic analysis

The linked list is read from beginning to end and each node is visited in sequence. The problem requires us to print the linked list from end to end. This kind of reverse order operation can obviously be considered

A data structure with first in, last out characteristics is the stack.

Specific operations are as follows:

  • Into the stack:Iterate through the linked list, placing the values of each nodepushInto the stack.
  • The stack:Values each nodepopOut of the stack, stored in an array and returned.

3. Animation description

Video address: mp.weixin.qq.com/s/qhyrwQukm…

Iv. Picture description

Five, reference code

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode curNode = head;
        while(curNode ! =null) {
            stack.addLast(curNode.val);
            curNode = curNode.next;
        }
        
        int size = stack.size();
        int[] res = new int[size];
        
        for (int i = 0; i < size; i++) {
           res[i] = stack.removeLast();
        }
        returnres; }}Copy the code

6. Complexity analysis

Time complexity

The time complexity is O(N), and O(N) time is used for both loading and unloading

Spatial complexity

The space complexity is O(N), and the auxiliary stack stack and array RES together use O(N) of extra space.

7. Relevant labels

  • The list

  • The stack