Print the linked list from end to end

The question

Print the linked list from end to end

solution

Here the output is returned as an array. The first is sequential traversal + reverse output. There are three ways to reverse the output.

1. Iterate over the addend group inversion

The list is iterated sequentially to add the list elements to the array, and then the array is reversed.

2. Use secondary stacks to achieve inversion

The list is iterated sequentially to add the list elements to the stack, and then the stack elements are returned from the stack to the array.

3. Use recursion to achieve reverse output

The value of the current node is the last element of the array, and the values of the following nodes are concatenated to precede the value of the current node.

code

1. Iterate over the addend group inversion

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {number[]}* /
var reversePrint = function(head) {
    let p = head
    let res = []
    if(! head)return res
    while(p){
        res.push(p.val)
        p = p.next
    }
    return res.reverse() 
};

Copy the code

2. Use secondary stacks to achieve inversion

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {number[]}* /
var reversePrint = function(head) {
    let p = head
    let stack = []
    let res = []
    if(! head)return res
    while(p){
        stack.push(p.val)
        p = p.next
    }
    while(stack.length>0){
        res.push(stack.pop())
    }
    return res
};

Copy the code

3. Use recursion to achieve reverse output

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {number[]}* /
var reversePrint = function(head) {
    return head == null ? [] : reversePrint(head.next).concat(head.val)
};

Copy the code