javascript实现链表数据结构和反转单链表方法

对于一个切图调接口写vue写久了的前端er来说，这还挺有趣的，也比较初级，算法大佬直接忽略吧。

1 js实现单链表

链表是什么，和数组有什么区别，这个就不展开说明了。原生js没有链表，所以封装一个简易版的。代码如下，其实一点也不难。

function LinkedList() {
    // 封装一个Node类, 用于保存每个节点信息
    function Node(element) {
        this.element = element
        this.next = null
    }

    // 链表中的属性
    this.length = 0
    this.head = null
    
    // 链表尾部追加元素方法
    LinkedList.prototype.append = function (element) {
        // 1.根据新元素创建节点
        var newNode = new Node(element)

        // 2.判断原来链表是否为空
        if (this.head === null) { // 链表尾空
            this.head = newNode
        } else { // 链表不为空
            // 2.1.定义变量, 保存当前找到的节点
            var current = this.head
            while (current.next) {
                current = current.next
            }

            // 2.2.找到最后一项, 将其next赋值为node
            current.next = newNode
        }

        // 3.链表长度增加1
        this.length++
    }
}

那么这个方法实现的是什么呢？

    var list = new LinkedList()
    list.append(1)
    list.append(2)
    list.append(3)
    list.append(4)
    console.log(list)

打印结果如下

再进一步展开的话

用js来解释的话，链表是个对象，有length属性以及head属性，同时head也是对象，这个对象有属性element和next

继续展开

链表就像它的名字一样，是一个链条一直链下去，知道最后一个节点的next为null。

2 实现单链表的意义

对于一个前端er来说，数组完全够用了，还有那么多好用的方法，为什么要自己封装一个这个呢？

答：上面的不了解，没办法做面试题。面试官问你算法了解吗？你说知道一些，然后就问你链表的问题了，最最基本的，链表和数组有啥区别，得知道吧，其次链表有什么特点，这个也得知道啊，要不然让你反转个单链表怎么反转啊？

3 如何反转一个单链表

就拿上述的链表为例，怎么实现4-3-2-1-null？实现如下图的结果

其实看似很简单的，想法也很直观，就是把链表最后一个节点作为头节点，第一个节点的指向指null，每个节点的next指向它的前驱节点。道理都懂，代码可能就不是那么好写了。不信前端er们不要往下看，自己试着写写，所以说，面试时候让你手写的反转单链表，是有理由的。

function myReverse (linkedList) {
    // 1 拿到传参链表的head
    var head = linkedList.head

    // 2 边界判断 如果头结点是空 或者只有一个结点 那还反转个啥
    if(head === null || head.next === null) return linkedList

    // 3 用三个指针
    var current = head
    var pre = null 
    var next = null
    while(current != null) {
        next = current.next
        current.next = pre
        pre = current
        current = next
    }
    linkedList.head = pre
}

其实真的不难，主要就是一个思维的转换。这里记录一下自己的理解，反正也是写给我自己看的。 myRevese函数接受参数链表，首先拿出链表的head。之后做边界判断。然后重点就是怎么做next指针的替换。第一点，对于链表的遍历，没有数组的for map等。链表的遍历只能人肉的一个节点一个节点的往下找。所以这段代码是必须的

    var current = head
    var next = null
    while(current != null) {
        next = current.next
        current = next
    }

只有这样才能保证链表遍历完成。

回到myRevese函数本身，初始化阶段 current = head，pre，next都为空。
第一次循环，next要先保存current的next，不先保存的话，下一步current.next指向就要改为指向它的前一个节点了
current.next = pre 反转嘛，当前的节点next肯定得修改，指向他的前驱节点
current就要变成current.next了，那变完之后，current的前一个节点就是current本身吧。所以 pre = current
current = next ，之前保存的变量用到了
直到最后一个，current为最后一个节点的时候的那次循环，current变成了current.next,也就是current为null了，所以要重新定义链表的head指向，指向的为pre，而不是current。

4 小结

对于一个切图掉接口写vue写久了的前端er来说，这还挺有趣的，算法大佬直接忽略吧。

javascript实现链表数据结构 和 反转单链表方法

1 js实现单链表

2 实现单链表的意义

3 如何反转一个单链表

4 小结

javascript实现链表数据结构和反转单链表方法