链表的区别

链表也分为单链表和双链表。

  • 单链表：每个节点包含 value 和 next，next 指向下一个节点
  • 双链表：每个节点包含 prev、value 和 next，prev 指向前一个节点，next 指向下一个节点

单链表的实现

class Node{
    constructor(value){
        this.value = value
        this.next = null
    }
}

class MyLinkedList{
    constructor(){
        this.head = null
        this.length = 0
    }
    // 按索引获取节点 value
    get(index){
        if(index >= 0 && index < this.length){
            let current = this.head
            if(index === 0){
                return current.value
            }else{
                let position = 0
                while(position < index){
                    current = current.next
                    position++
                }
                return current.value
            }
        }
        return -1
    }
    // 在头部添加节点
    addAtHead(val){
        const node = new Node(val)
        let current = this.head
        this.head = node
        this.head.next = current
        this.length++
    }
    // 添加节点到尾部
    addAtTail(val){
        const node = new Node(val)
        if(this.length){
            let current = this.head
            while(current.next){
                current = current.next
            }
            current.next = node
        }else{
            this.head = node
        }
        this.length++
    }
    // 在给定位置添加节点
    addAtIndex(index, val){
        const node = new Node(val)
        let position = 0
        let current = null
        let previous = null
        let length = this.length
        if(length === 0 && index <= 0){
            this.head = node
            this.length++
        }else if (index <= 0){
           this.addAtHead(val)
        }else if(index === length){
            this.addAtTail(val)
        }else if(index > 0 && index < length){
            current = this.head
            while(position < index){
                previous = current
                current = current.next
                position++
            }
            previous.next = node
            node.next = current
            this.length++
        }
    }
    // 按索引删除
    deleteAtIndex(index){
        if(index >= this.length) return
        let current = this.head
        let previous = null
        let position = 0
        if(index === 0 && index === this.length){
            this.head = null
        }else if(index === 0 ){
            this.head = current.next
        }else{
            while(position < index){
                previous = current
                current = current.next
                position++
            }
            previous.next = current.next
        }
        this.length--
    }
}

双链表的实现

class Node{
    constructor(value){
        this.value = value
        this.next = null
        this.prev = null
    }
}

class MyLinkedList{
    constructor(){
        this.head = null
        this.length = 0
    }
    get(index){
        if(index >= 0 && index < this.length){
            let current = this.head
            if(index === 0){
                return current.value
            }else{
                let position = 0
                while(position < index){
                    current = current.next
                    position++
                }
                return current.value
            }
        }
        return -1
    }
    addAtHead(val){
        const node = new Node(val)
        let current = this.head
        this.head = node
        this.head.next = current
        this.length++
        if(this.length === 1){
            return
        }else{
            current.prev = this.head
        }
    }
    addAtTail(val){
        const node = new Node(val)
        if(this.length){
            let current = this.head
            while(current.next){
                current = current.next
            }
            current.next = node
            node.prev = current
        }else{
            this.head = node
        }
        this.length++
    }
    addAtIndex(index, val){
        const node = new Node(val)
        let position = 0
        let current = null
        let previous = null
        let length = this.length
        if(length === 0 && index <= 0){
            this.head = node
            this.length++
        }else if (index <= 0){
           this.addAtHead(val)
        }else if(index === length){
            this.addAtTail(val)
        }else if(index > 0 && index < length){
            current = this.head
            while(position < index){
                previous = current
                current = current.next
                position++
            }
            previous.next = node
            current.prev = node
            node.prev = previous
            node.next = current
            this.length++
        }
    }
    deleteAtIndex(index){
        if(index >= this.length) return
        let current = this.head
        let previous = null
        let position = 0
        if(index === 0 && this.length === 1){
           this.head = null
        }else if(index === 0){
            this.head = current.next
            current.next.prev = null
        }else{
            while(position < index){
                previous = current
                current = current.next
                position++
            }
            if(index === this.length - 1){
                previous.next = null
            }else{
                previous.next = current.next
                current.next.prev = previous
            }
        }
        this.length--
    }
}

环形链表

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。

解法：双指针遍历 首先明确一个结论：head到入环点的距离 等于 相遇点到入环点的距离，推演过程有空补图=。=

var detectCycle = function(head) {
    if(!head || !head.next) return null
    let fastPoint = head
    let slowPoint = head
    while(fastPoint && fastPoint.next){
        fastPoint = fastPoint.next.next
        slowPoint = slowPoint.next
        if(fastPoint === slowPoint) {
            slowPoint = head
            while(fastPoint !== slowPoint){
                fastPoint = fastPoint.next
                slowPoint = slowPoint.next
            }
            return slowPoint
        }
    }
    return null
};