剑指 Offer 06. 从尾到头打印链表

题目

力扣-剑指 Offer 06. 从尾到头打印链表

我的复述：

链表的最后一个节点变为数组的头部，相当于将链表反转以后，用数组的形式将反转后的链表节点输出。

题解

解法一：两个for循环

• 1，先声明两个整型数组；
• 2，第一个for循环从头到尾记录链表的每个节点的值；
• 3，第二个for循环逆序记录链表的每个节点的值。

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    var re []int  //正序
    var er []int  //逆序
    for ;head != nil; {
        re = append(re,head.Val)  //从头到尾记录链表的每个节点的值
        head = head.Next
    }
    for i:=len(re)-1;i>=0;i-- {
        er = append(er,re[i])  //逆序记录链表的每个节点的值
    }
    return er  //返回
}

leetcode-cn执行：

执行用时：
0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：
3.5 MB, 在所有 Go 提交中击败了46.84%的用户

牛客网执行：

运行时间：3ms
超过2.29%用Go提交的代码
占用内存：868KB
超过39.69%用Go提交的代码

解法二：递归

两种解法：栈与递归

• 递归函数作用：将链表节点值逆序存入结果集
• 结束条件：当节点为空时
• 递归调用条件：当下一个节点不为空时

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return []int{}
    }
    res := reversePrint(head.Next)
    return append(res, head.Val)
}

leetcode-cn执行：

执行用时：
4 ms, 在所有 Go 提交中击败了63.34%的用户
内存消耗：
4.7 MB, 在所有 Go 提交中击败了28.61%的用户

牛客网执行：

运行时间：3ms
超过2.29%用Go提交的代码
占用内存：868KB
超过39.69%用Go提交的代码

解法三：栈

• 1，构建一个栈，将链表里的节点依次压入这个栈中；
• 2，初始化一个数组，再从栈中取出值放入数组中。

//java
/**
 * 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<>();
        //构建一个指针，指向链表的头结点位置，从它开始向后遍历
        ListNode curNode = head;
        //不断的遍历原链表中的每个节点，直到为null
        while ( curNode != null) {
            //把每个节点的值加入到栈中
            stack.push(curNode.val);
            //curNode向后移动
            curNode = curNode.next;
        }
        //获取栈的长度
        int size = stack.size();
        //定义一个同样长度的数组 res
        int[] res = new int[size];
        //遍历栈，从栈顶挨个弹出每个值，把这些值依次加入到数组res中
        for (int i = 0;i < size;i++) {
            //数组接收栈顶元素值
            res[i] = stack.pop();
        }
        //返回结果
        return res;
    }
}

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    //构建一个栈，用来存储链表中每个节点的值
    stack := make([]int,0)
    //构建一个指针，指向链表的头结点位置，从它开始向后遍历
    curNode := head
    //不断的遍历原链表中的每个节点，直到为nil
    for curNode != nil {
        //把每个节点的值加入到栈中
        stack = append(stack,curNode.Val)
        //curNode向后移动
        curNode = curNode.Next
    }
    //获取栈的长度
    size := len(stack)
    //定义一个同样长度的数组 res
    res := make([]int,size)
    //遍历栈，从栈顶挨个弹出每个值，把这些值依次加入到数组res中
    for i := 0;i < size;i++ {
        //数组接收栈顶元素值
        res[i] = stack[len(stack)-i-1]
    }
    
    return res
}

leetcode-cn执行用时：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了51.87%的用户