LeetCode精选Top面试题之反转链表

这是我参与更文挑战的第3天，活动详情查看： 更文挑战

前言

公众号给npy的前端秘籍

加vx?16639199716,拉你进群嗷~❤️

数据结构中的链表还是很重要的，所以本次学习一下链表，做一下总结，分享给大家?

数组的缺点

数组并不总是组织数据的最佳数据结构。

原因如下：在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，要再加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦。因为需要将数组中的其他元素向前或者向后平移以反映数组刚刚进行了添加或者删除操作。

链表

一种常见的基础数据结构，也是一种线性表，但是并不会按线性表的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。即链表是由一组节点组成的集合，元素存储不连续，每个节点都使用一个对象的引用指向它的后继。

链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而顺序表相应的时间复杂度分别是 O(log n) 和 O(1)。

优缺点：

• 使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
• 链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

Tips:
?

「如果你发现数组在实际使用时很慢，就可以考虑用链表来替代它。除了对数据的随机访问，链表几乎可以在任何可以使用一维数据的情况中。如果谁要随机访问，数组仍然是最好的选择。」

设计一个基于对象的链表

我们设计的链表包含两个类。Node类用来表示节点，LinkedList类提供了插入节点、删除加点、显示列表元素的方法，以及其他的一些辅助方法。

Node类

Node类包括两个属性：element用来保存节点上的数据，next用来保存指向下一个节点的链接。我们使用一个构造函数来创建节点，该构造函数设置了这两个属性的值：

       class Node {
            constructor(element) {
                this.element = element;
                this.next = null;
            }
        }
        
复制代码

LinkedList类

LinkedList类提供了对链表的操作方法。

//单链表插入、删除、查找
        function LinkedList() {
            this.head = new Node(val)
            this.findByVal= findByVal
            this.insert = insert
            this.remove = remove
            this.diaplay = display
        }
   
            // 找val值节点，没有找到返回-1
            findByVal(val) {
                let current = this.head
                while (current !== null && current.element !== val) {
                    current = current.next
                }
                return current ? current : -1
            }

            // 插入节点,在值为val后面插入
            insert(newElement, val) {
                let current = this.findByVal(val)
                if (current === -1) return false
                let newNode = new Node(newElement)
                newElement.next = current.next
                current.next = newElement
            }

            // 获取值为nodeVal的前一个节点,找不到为-1,参数是val
            // 适用于链表中无重复节点
            findNodePreByVal(nodeVal) {
                let current = this.head;
                while (current.next !== null && current.next.element !== nodeVal)
                    current = current.next
                return current !== null ? current : -1
            }

            // 根据index查找当前节点, 参数为index
            // 可以作为比较链表是否有重复节点

            findByIndex(index) {
                let current = this.head,
                    pos = 1
                while (current.next !== null && pos !== index) {
                    current = current.next
                    pos++
                }

                return (current && pos === index) ? current : -1
            }

            // 删除某一个节点,删除失败放回false
            remove(nodeVal) {
                if(nodeVal === 'head') return false
                let needRemoveNode = this.findByVal(nodeVal)
                if (needRemoveNode === -1) return false
                let preveNode = this.findNodePreByVal(nodeVal)
                
                preveNode.next = needRemoveNode.next
            }

            //遍历节点

            disPlay() {
                let res = new Array()
                let current = this.head
                while (current !== null) {
                    res.push(current.val)
                    current = current.next
                }
                return res
            }

            // 在链表末尾插入一个新的节点
            push(nodeVal) {
                let current = this.head
                let node = new Node(nodeVal)
                while (current.next !== null) {
                    current = current.next
                    current.next = node
                }
            }
            // 在头部插入
            frontPush(nodeVal) {
                let newNode = new Node(nodeVal)
                this.insert(nodeVal,'head')
            }
        }
复制代码

[LeetCode206、反转链表]

题目描述：反转一个单链表。

链接：[leetcode]反转一个链表

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

• 反转两个节点，将n+1的next指向n
• 反转多个节点：双指针遍历链表，重复以上操作
• 思路
  • 双指针一前一后遍历链表
  • 反转双指针

var reverseList = function (head) {
    let p1 = head;
    let p2 = null;
    while(p1){
        const tmp =p1.next
        p1.next=p2;
        p2=p1;
        p1=tmp;
    }
    return p2;
};
//时间复杂度O(n)
//空间复杂度O(1)
复制代码

今日加餐

今日加餐我选择了LeetCode237、删除链表中的节点，两个一起恰，味道更好嗷~

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

• 思路
  • 将被删节点的值改为下个节点
  • 删除下个节点

var deleteNode = function(node) {
    node.val = node.next.val;
    node.next=node.next.next
};
//时间复杂度空间复杂度都是O(1)
复制代码

总结

刷题打卡第9天，选择力扣第206、237题，学习了链表的相关知识，一起加油哇~

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话：
点赞支持下吧，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）关注公众号给npy的前端秘籍，我们一起学习一起进步。
觉得不错的话，也可以阅读其他文章（感谢朋友的鼓励与支持???）

开启LeetCode之旅

LeetCode之双指针

Leet27、移除元素

前端工程师必学的经典排序算法

LeetCode20、括号匹配

LeetCode7、整数反转

LeetCode344、反转字符串