Subject to introduce

Leetcode-cn.com/problems/co…

Method 1: stack

The stack is characterized by last in, first out, that is, the last element pushed onto the stack is the first to pop out. Considering this feature of the stack, the stack is used to reverse the order of the linked list elements. Starting at the head of the list, push each node onto the stack in turn, and then pop the stack elements in turn and store them in the array.

Create a stack to store the nodes of the linked list, create a pointer that initially points to the head node of the list, and repeat the following operations when the pointer points to a non-empty element:

• Pushes the node to which the pointer points onto the stack
• Moves the pointer to the next node of the current node
• Get the stack size and create an array print with size
• Create a subscript and initialize index = 0
• Repeat the following operations size times:
  • Pop a node from the stack and store the value of that node to print[index]
  • Increment index by 1
• Return to the print

The code is as follows:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode tempHead = head;
        Stack<ListNode> stack = new Stack<>();
        while(tempHead ! =null) {
            stack.push(tempHead);
            tempHead = tempHead.next;
        }
        int  n = stack.size();
        int[] print = new int[n];
        for(int i = 0 ; i < n ; i++) {
            print[i] = stack.pop().val;
        }
        returnprint; }}Copy the code

Complexity analysis

• Time complexity: O(n). Traversing the list forward and then popping all the nodes off the stack is equivalent to traversing the list backward again.
• Space complexity: O(n). An additional stack is used to store each node in the linked list.

Method two: recursion

Since the idea of using a stack, and recursion is essentially a stack structure, to achieve the reverse output of the linked list, each time a node is visited, first recursively output the node behind it, and then output the node itself, so the output of the linked list is reversed.

• Recursion phase: every time head. Next is passed, head == null is used as the recursive termination condition.

• Backtracking phase: When backtracking layer by layer, add the current node value to the list, namely tmp.add(head.val). Finally, convert the list TMP to the array RES and return.

The code is as follows:

class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }
    void recur(ListNode head) {
        if(head == null) {
            return; } recur(head.next); tmp.add(head.val); }}Copy the code

Complexity analysis

• Time complexity O(N) : Traverses the linked list, recursively N times.
• Space complexity O(N) : System recursion requires O(N) stack space.