登录
原创

JS基础算法(数据结构之链表篇)

专栏JS算法基础篇
发布于 2020-12-15 阅读 2295
  • 前端
  • 面试
  • 算法
原创

数据结构之链表

  • 知识点
    如何手动地创建一个链表的数据结构(NodeList)
    知道链表如何排序(sort)
    如何检测链表是否是闭环的
  • 概念
    链表由一系列结点(元素)组成,结点可以在运行时动态生成。每个结点包括两个部分:存储数据元素的数据域和存储下一个结点地址的指针域。
    链表只暴露一个头指针,后面的元素必须通过头指针不断的next,才能拿到
  • js中没有链表结构
    数组可以充当队列,可以充当堆栈,但是不能充当链表

排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

什么是快速排序?
选择一个基准值,小于的放它左边,大于的放它右边,然后左边右边再选一个基准值,以此类推。

11.png
12.png

定义两个指针,q指针遍历所有链表节点,如果q指针指向的元素小于基准元素,就和p指针的后一个元素进行交换,同时p后移一位。最后让基准元素和小于它的后一个元素进行交换

// 声明链表的节点

class Node {
    constructor(value) {
        this.val = value;
        this.next = undefined
    }
}

// 声明链表的数据结构

class NodeList {
    constructor(arr) {
        // 声明链表的头部节点
        let head = new Node(arr.shift())
        let next = head
        arr.forEach(item => {
            next.next = new Node(item)
            next = next.next
        })
        return head
    }
}

// 交换两个节点的值
let swap = (p, q) => {
    let val = p.val
    p.val = q.val
    q.val = val
}

// 寻找基准元素的节点
let partion = (begin, end) => {
    let val = begin.val
    let p = begin
    let q = begin.next
    while (q !== end) {
        if (q.val < val) {
            p = p.next
            swap(p, q)
        }
        q = q.next
    }
    // 让基准元素跑到中间去
    swap(p, begin)
    return p
}

export default function sort(begin, end) {
    if (begin !== end) {
        let part = partion(begin, end)
        sort(begin, part)
        sort(part.next, end)
    }
}

export {
    Node,
    NodeList
}
// 拿到头指针
let head =new NodeList([4,1,3,2,7,9,10,12,6])
// 对头指针进行排序
sort(head)
let res=[]
let next=head
while(next){
    res.push(next.val)
    next=next.next
}
console.log(res)// [1,2,3,4,6,7,9,10,12]
const merge = (l, r) => {
    let result = new ListNode('sb');
    let current = result;

    while(l && r) {
        if(l.val < r.val) {
            current.next = l;
            l = l.next;
            current = current.next;
        } else {
            current.next = r;
            r = r.next;
            current = current.next;
        }
    }

    current.next = l || r;
    return result.next;
}

// 归并排序
var sortList = function(head) {
    if(head === null || head.next === null) return head;
    let fast = head;
    let slow = head;

    while(fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    }

    const mid = slow.next;
    slow.next = null;

    return merge(sortList(head), sortList(mid));
};

环形链表

给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:
你能用 O(1)(即,常量)内存解决此问题吗?

  • 环形检测原理
    两个指针一个快,一个慢,同时出发。快的和慢的相遇
    快的在慢的后面
// 声明链表的节点
class Node {
    constructor(value) {
        this.val = value;
        this.next = undefined
    }
}

// 声明链表的数据结构
class NodeList {
    constructor(arr) {
        // 声明链表的头部节点
        let head = new Node(arr.shift())
        let next = head
        arr.forEach(item => {
            next.next = new Node(item)
            next = next.next
        })
        return head
    }
}

export default function isCircle(head) {
    // 慢指针
    let slow = head
        // 快指针
    let fast = head.next
    while (1) {
        if (!fast || !fast.next) {
            return false
        } else if (fast === slow || fast.next === slow) {
            return true
        } else {
            slow = slow.next
            fast = fast.next.next
        }
    }
}
export {
    Node,
    NodeList
}
// 检测
let head=new NodeList([6,1,2,5,7,9])
// 设置环状
head.next.next.next.next.next.next=head.next
console.log(isCircle(head))// true

评论区

timing
4粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

0

举报