Sword finger offer06 Print linked list from end to end

The finger of the sword Offer06. Print linked list from end to end

Title Description

Enter the head node of a linked list , Return the value of each node from the end to the end （ Return with array ）.

Example 1：

 Input ：head = [1,3,2]
 Output ：[2,3,1]

Limit ：

0 <= Chain length <= 10000

JAVA Code ( Complete four methods )

It's easy to do a problem , But how to solve the problem in many ways , Think from multiple perspectives , Can we exercise our logical thinking ability more .

Reverse insertion

Get the length of the linked list and create an array , Traverse the linked list from the beginning , Insert array in reverse order .

/** * 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 p = head;
        int len = getLength(head);
        int[] arr = new int[len];
        int index = len-1;
        while(index>=0){
    
            arr[index] = p.val;
            p = p.next;
            index--;
        }
        return arr;
    }
    
    // Get the length of the list 
    public int getLength(ListNode head){
    
        ListNode p = head;
        int n = 0;
        while(p!=null){
    
            p = p.next;
            n++;
        }
        return n;
    }
}

Stack method

Stack linked list , Then put it out of the stack into the array .

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        Stack<Integer> stack = new Stack<Integer>();
        ListNode p = head;
        while(p!=null){
    
            stack.push(p.val);
            p = p.next;
        }
        int size = stack.size();
        int[] arr = new int[size];
        for(int i = 0;i<size;i++){
    
            arr[i] = stack.pop();
        }
        return arr;
    }
}

Reverse linked list method

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        // Reverse the linked list 
        ListNode p = head;
        if(p==null){
    
            return new int[0];
        }
        ListNode q = p.next;
        int len = 1;
        while(q!=null){
    
        	// Save the node of the next operation 
            ListNode next = q.next;
            q.next = p;
            p = q;
            q = next;
            len++;
        }
        // Handle tail nodes 
        head.next = null;

        int[] arr = new int[len];
        ListNode l = p;
        int index = 0;
        while(l!=null){
    
            arr[index++] = l.val;
            l = l.next;
        }
        return arr;
    }

    
}

ArrayList Law

Save the linked list data to ArrayList in , Then put it in the array in reverse order

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListNode p = head;
        int n = 0;
        while(p!=null){
    
            list.add(p.val);
            p = p.next;
            n++;
        }
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
    
            arr[i] = list.get(n-i-1);
        }
        return arr;
    }
}