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

简介: AC 剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]

限制:

0 <= 链表长度 <= 10000

import java.util.LinkedList;

class Solution {
    /**
     * @Title: reversePrint
     * @Description: 不使用Java的已有链表结构,而是自己通过哑结点方式实现头插
     * @author: itbird
     * @date 2022年3月15日 下午3:19:50
     * @param head
     * @return int[] 时间复杂度: O(N) 空间复杂度: O(N)
     */
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 构造哑结点,进行头插
        ListNode node = new ListNode(0);
        int size = 0;
        while (head != null) {
            size++;
            // 保存哑结点的next
            ListNode temp = node.next;
            // 将哑结点的next,指向新的节点
            node.next = new ListNode(head.val);
            // 将哑结点的next.next指向第一步保存的哑结点的next节点
            node.next.next = temp;
            head = head.next;
        }
        int[] result = new int[size];
        node = node.next;
        int i = 0;
        while (node != null) {
            result[i++] = node.val;
            node = node.next;
        }
        return result;
    }

    /**
     * @Title: reversePrint
     * @Description: 使用Java的LinkedList,遍历List,进行头插
     * @author: itbird
     * @date 2022年3月15日 下午3:19:50
     * @param head
     * @return int[] 时间复杂度: O(N) 空间复杂度: O(2N)
     */
    public int[] reversePrint1(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        LinkedList<Integer> linkedList = new LinkedList<>();
        while (head != null) {
            linkedList.addFirst(head.val);
            head = head.next;
        }
        int[] result = new int[linkedList.size()];
        for (int i = 0; i < linkedList.size(); i++) {
            result[i] = linkedList.get(i);
        }
        return result;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
目录
相关文章
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
49 0
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
54 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4
|
6月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
6月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
6月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
6月前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
6月前
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
|
6月前
剑指 Offer 18. 删除链表的节点
剑指 Offer 18. 删除链表的节点
44 0
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表