1. 链表介绍 #

• 链表是一种物理存储单元上非连续、非顺序的存储结构
• 链表由一系列结点(链表中每一个元素称为结点)组成
• 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
• 数据元素的逻辑顺序是通过链表中的指针链接次序实现的

2.链表实现 #

2.1 地址实现 #

• diagraming

//结点类
class ListNode {
    constructor(data, next) {
        //数据域 存储此结点的数据
        this.data = data;
        //指针域，指向下一个结点
        this.next = next;
    }
}
//链表类
class List {
    constructor() {
        this.size = 0;//结点数量
        this.head = null;//重置头指针
    }
    /**
     * 在指定索引数添加结点
     * @param {*} index 索引
     * @param {*} ListNode 结点
     */
    add(index, ListNode) {
        //如果要插入的索引为0
        if (index === 0) {
            //当前节点的下一个节点指定头节点
            ListNode.next = this.head;
            //头结点指定当前要插入的节点
            this.head = ListNode;
        } else {
            //获取要插入的节点的前一个节点
            let prev = this.get(index - 1);
            //当前插入节点的下一个节点指定pre的下一个节点
            ListNode.next = prev.next;
            //pre的下一个节点指定当前要插入的节点
            prev.next = ListNode;
        }
        //长度加1
        this.size++;
    }
    /**
     * 判断要获取的索引是否越界
     * @param {*} index 
     */
    rangeCheck(index) {
        if (index < 0 || index >= this.size) {
            throw new Error('索引越界');
        }
    }
    /**
     * 获取指定索引的结点对象
     * @param {*} index 
     * @returns 
     */
    get(index) {
        this.rangeCheck(index);
        let curr = this.head;
        while (index--) {
            curr = curr.next;
        }
        return curr;
    }
    /**
     * 删除索引入对应的结点
     * @param {*} index 
     */
    remove(index) {
        this.rangeCheck(index);
        if (index === 0) {
            this.head = this.head.next;
        } else {
            let prev = this.get(index - 1);
            prev.next = prev.next.next;
        }
    }
    /**
     * 清空链表
     */
    clear() {
        this.head = null;
        this.size = 0;
    }
    /**
     * 打印所有节点的数据
     */
    print() {
        //先让当前指针指向头指针 
        let curr = this.head;
        let str = '';
        while (curr) {
            //拼上当前的数据域
            str += curr.data + '->';
            //让当前指针指向下一个结点
            curr = curr.next;
        }
        str += 'null';
        console.log(str);
    }
}

let list = new List();
//添加a结点
let a = new ListNode('A');
list.add(0, a);
//添加c结点
let c = new ListNode('C');
list.add(1, c);
//添加b节点
let b = new ListNode('B');
list.add(1, b);
//删除b节点
list.remove(1);
//头部添加d节点
let d = new ListNode('D');
list.add(0, d);
//打印所有节点
list.print();//D->A->C->null

2.2 数组实现 #

• diagraming

class List {
    constructor(head, value) {
        //存放结点的数据
        this.data = [];
        //存放结点的索引下标
        this.next = [];
        this.head = head;
        this.data[this.head] = value;
    }
    add(index, nextIndex, value) {
        this.next[index] = nextIndex;
        this.data[nextIndex] = value;
    }
    print() {
        //先让当前指针指向头指针 
        let curr = this.head;
        let str = '';
        while (curr) {
            //拼上当前的数据域
            str += this.data[curr] + '->';
            //让当前指针指向下一个结点
            curr = this.next[curr];
        }
        str += 'null';
        console.log(str);
    }
}
let head = 2;
let list = new List(head, 'A');
list.add(head, 4, 'B');
list.add(4, 6, 'C');
list.add(6, 0, 'D');
console.log(list.next.join(''));//460
console.log(list.data.join(''));//DABC
list.print();

3.leetcode #

3.1 linked-list-cycle #

• linked-list-cycle
• processon

var hasCycle = function (head) {
    if (head === null) return false;
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast)
            return true;
    }
    return false;
};

3.2 linked-list-cycle-ii #

• linked-list-cycle-ii
• diagraming1
• diagraming2

var detectCycle = function(head) {
    if (head === null) return head;
    let slow = head;
    let fast = head;
    let isCycle = false;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast){
            isCycle = true;
            break;
        }
    }
    if (!isCycle) {
        return null;
    }
    fast = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};