【剑指offer】3.从尾到头打印链表
导读：
分类：技术干货
题目：从尾到头打印链表
一起重温《剑指offer》，再也不怕手写算法啦！
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个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<index){
preNode = currentNode;
currentNode = currentNode.next;
currentIndex++;
}
preNode.next = node;
node.next = currentNode;
this.length++;
}
}
}链表翻转
把初始链表头当做基准点
移动下一个元素到头部
直到下一个元素为空
/**
* 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;
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-01-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
