【剑指offer】3.从尾到头打印链表

graf 发布于2019-08-23 14:37 / 3220人阅读

摘要：题目描述输入一个链表，按链表值从尾到头的顺序返回一个。最后别忘了，从尾到头遍历链表，不要忘了将你的结果进行翻转。

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

分析

要了解链表的数据结构：

val属性存储当前的值，next属性存储下一个节点的引用。

要遍历链表就是不断找到当前节点的next节点，当next节点是null时，说明是最后一个节点，停止遍历。

最后别忘了，从尾到头遍历链表，不要忘了将你的结果进行翻转。

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    const result = [];
    let temp = head;
    while(temp){
        result.push(temp.val);
        temp = temp.next;
    }
    return result.reverse();
}

拓展

链表定义：用一组任意存储的单元来存储线性表的数据元素。

一个对象存储着本身的值和下一个元素的地址。

需要遍历才能查询到元素，查询慢。

插入元素只需断开连接重新赋值，插入快。

        function LinkList(){
            function node(element){
                this.value = element;
                this.next = null;
            }
            let length = 0;
            let head = null;
        }
        LinkList.prototype = {
            // 追加
            append:function(element){
                var node = new node(element);
                var temp = this.head;
                if(this.head){
                    //遍历找到链表的终点
                    while(temp.next){
                        temp = temp.next;
                    }
                    temp.next = node;
                }else{
                    this.head = node;
                }
                this.length++;
            },
            // 插入
            insert:function(element,index){
                if(index <= this.length && index>0){
                    var node = new node(element);
                    var currentIndex = 0;
                    var currentNode = this.head;
                    var preNode = null;
                    if (currentIndex === 0) {
                        node.next = currentNode;
                        this.head = node;
                        return;
                    }
                    while(currentIndex
链表翻转
把初始链表头当做基准点
移动下一个元素到头部
直到下一个元素为空
    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function (head) {
      let currentNode = null;
      let headNode = head;
      while (head && head.next) {
        // 将当前节点从链表中取出
        currentNode = head.next;
        head.next = currentNode.next;
        // 将取出的节点移动到头部
        currentNode.next = headNode;
        headNode = currentNode;
      }
      return headNode;
    };

云服务器 GPU云服务器剑指找不到头文件 offer webrtc offer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100877.html

剑指offer系列——剑指 Offer 06. 从尾到头打印链表（C语言）

摘要：导航小助手剑指从尾到头打印链表题目详情解题思路源代码总结剑指从尾到头打印链表题目详情输入一个链表的头节点，从尾到头反过来返回每个节点的值用数组返回。时间复杂度方法先反转链表并求长度，在将反转后的链表数据拷贝至数组中。 ...

DevTTL 2021-09-04 16:41 评论0 收藏0
#yyds干货盘点#剑指 Offer 06. 从尾到头打印链表

摘要：题目输入一个链表的头节点，从尾到头反过来返回每个节点的值用数组返回。题目输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。示例 1：输入：head = [1,3,2]输出：[2,3,1]限制：0

SQC 2021-11-23 09:51 评论0 收藏0
剑指offer【6】：从尾到头打印链表

题目输入一个链表的头节点，从尾到头反过来打印出每个节点的值。解题思路一、栈第一个遍历的节点最后一个输出，而最后一个比遍历到的节点第一个输出（后进先） public static ArrayList printListFromTailToHead(ListNode listNode){ ArrayList list = new ArrayList(); ...

Kahn 2019-08-16 18:39 评论0 收藏0
剑指Offer(Java版) 持续更新中

摘要：面试题从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值面试题重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。队列中的元素为类型。其中负数用补码表示。面试题2 单例(之前有整理，略) 面试题3 二维数组中的查找 public boolean find(int target, int [][] arra...

justCoding 2019-08-15 11:04 评论0 收藏0
利用PHP实现《剑指 offer》之链表（数据结构与算法实战）

摘要：一定要认真看分析注释题目要求题目描述输入一个链表，从尾到头打印链表每个节点的值。分析因为链表只有知道当前结点才能知道下一结点，所以不可能直接从后往前打印。一定要认真看分析 | 注释 | 题目要求 Question 1 题目描述：输入一个链表，从尾到头打印链表每个节点的值。分析：因为链表只有知道当前结点才能知道下一结点，所以不可能直接从后往前打印。这种逆序的算法（策略）我们常用栈这...

hiYoHoo 2019-06-28 18:48 评论0 收藏0