链表

链表定义:用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址

特点:查询慢-需要遍历才能查询到元素; 插入快-插入元素只需断开连接重新赋值;

链表遍历

// head链表头节点
// .value表示链表该节点存储的数据
// .next指向下一个节点
var p = head;
while(p!=null){
    console.log(p.value);
    p = p.next;
}

链表双指针

示例:

单链表的中间节点:力扣876

给定一个头结点为 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

问题的关键也在于我们⽆法直接得到单链表的⻓度 n,常规⽅法也是先遍历链表计算 n,再遍历⼀次得到第 n / 2 个节点,也就是中间节点。如果想⼀次遍历就得到中间节点,也需要耍点⼩聪明,使⽤「快慢指针」的技巧:我们让两个指针 slowfast 分别指向链表头结点 head。每当慢指针 slow 前进⼀步,快指针 fast 就前进两步,这样,当 fast ⾛到链表末尾时,slow 就指向了链表中点。

function middleNode(head){
    // 快慢指针
    var slow = head;
    var fast = head;
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

示例:

环形链表:力扣141

给你一个链表的头节点 head ,判断链表中是否有环。

每当慢指针 slow 前进⼀步,快指针 fast 就前进两步。如果 fast 最终遇到空指针,说明链表中没有环;如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow n圈,说明链表中含有环。只需要把寻找链表中点的代码稍加修改就⾏了:

function hasCycle(head){
    var slow = head;
    var fast = head;
    while(fast!=null&&fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast==slow){
            return true
        }
    }
    return false
}
文档更新时间: 2022-04-27 17:40   作者:张老师