“Finger Offer 06. Print the linked list from end to end”

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic Description (Simple level)

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

Given the already defined linked list structure ListNode is shown below

public class ListNode {
   private int val;
   private ListNode next;
   public ListNode(int x) { val = x; }}Copy the code
The sample
Enter: head = [1.3.2] output: [2.3.1]
Copy the code
Train of thought Analysis (Auxiliary stack)

Singly linked list structure features, the current node points to the next node reference, can only be accessed from front to back each node. If you want to print the list from the end, the first reaction is to “reverse” the list and print it. Reverse order printing is a first-in, last-out data structure, so it is obvious that the stack is a first-in, last-out data structure. Consider using a secondary stack that pushes the data as it traverses the list and then exits the stack.

Code implementation (auxiliary stack)
class Solution {
    public int[] reversePrint(ListNode head) {
       Stack<ListNode> stack = new Stack<>();
       ListNode temp = head;
       while (null! = temp) { stack.push(temp); temp = temp.next; }int size = stack.size();
       int[] print = new int[size];
       for (int i = 0; i < size; i++) {
           print[i] = stack.pop().val;
       }
       returnprint; }}Copy the code
Analysis of ideas (Recursion)

The traversal feature of linked lists, where the last node points to NULL, is an obvious feature. Usually when we write recursive calls, there’s an exit, and this exit is pretty clear. But I’m not alone in finding that many of my peers are a little bit averse to recursion. The reason is probably that it is awkward to write and does not conform to people’s way of thinking, but I think that the recursive thought is “really thinking from the perspective of a computer”. Back to the topic, print the linked list from the end, using the idea of recursion, recursion is divided into two stages: recursive stage, backtracking stage; The exit for the recursive phase has been found, and as the traversal goes on when head == NULL, the recursive phase ends, and then we go back, at which point we simply add the values of the corresponding nodes to an array (in reverse order), and finally return the temporary array and print it.

Code implementation (recursive)
class Solution {
    int m = 0, n = 0;
    int[] result;

    public int[] reversePrint(ListNode head) {
        recursion(head);
        return result;
    }

    public void recursion(ListNode head) {
        if (null == head) {
            result = new int[m];
            return; } m++; recursion(head.next); result[n] = head.val; n++; }}// Where m and n represent the capacity of the array and the subscript of the corresponding value
Copy the code
Time complexity
  • Auxiliary stack

The time complexity is O(N) : contains the operation of traversing the linked list and the stack.

Space complexity is O(N) : introduce auxiliary stacks, arrays.

  • recursive

Time complexity is O(N) : traverses the entire list.

Spatial complexity O(N) : Recursion depth is related to list size.

link

LeetCode