数据结构与算法：链表

链表简介

链表是一种常见的数据结构，是一种线性表。它不会按线性顺序存储数据，相对于数组，它不需要开辟连续的存储空间。链表适合插入或者删除操作比较频繁的场景，时间复杂度为O(1)；但是因为不能按下标访问元素，其查询效率较低，时间复杂度为O(n)。链表的节点有一个用于存储数据的属性，本文称作 val ，然后还有个 next 指针用于指向下一个节点，这样节点一个一个连接就构成链表了。链表类型主要有 单链表，双向链表，循环链表 。关于更多的内容，可查看 维基百科-链表。

单链表

单链表的表现形式如下图所示：

单链表也叫单向链表，顾名思义，它只有一个方向，也就是只有一个next指针用于指向下个节点。知道了单链表的结构表现之后，我们可以开始写代码来创建单链表了。

单链表的节点结构：

class ListNode {
    constructor(val) {
    	// 用于保存数据
        this.val = val
        // 用于指向下个节点
        this.next = null
    }
}

单链表的创建以及添加元素和删除元素方法：

class LinkedList {
    constructor(val) {
        this.head = new ListNode(val)
        this.size = 1
    }

    append(val) {
        if (!this.head) {
            this.head = new ListNode(val)
            return
        }

        const newNode = new ListNode(val)
        let p = this.head

        while (p.next) {
            p = p.next
        }

        p.next = newNode
        this.size++
    }

    deleteByVal(val) {
        // 虚拟头节点，便于删除头节点
        const dummyHead = new ListNode(0)
        dummyHead.next = this.head
        let p = dummyHead

        while (p.next && p.next.val !== val) {
            p = p.next
        }

        // 不存在该节点，返回-1
        if (!p.next) {
            return -1
        }

        p.next = p.next.next
        this.head = dummyHead.next
        this.size--
    }

    deleteByIndex(index) {
        if (index > this.size || index <= 0) {
            return -1
        }

        const dummyHead = new ListNode(0)
        dummyHead.next = this.head
        let p = dummyHead, i = 1

        while (p.next && i !== index) {
            p = p.next
            i++
        }

        p.next = p.next.next
        this.head = dummyHead.next
        this.size--
    }

    traversal() {
        const res = []
        let p = this.head

        while (p) {
            res.push(p.val)
            p = p.next
        }

        console.log(res)
    }
}


const linkedList = new LinkedList(0)
linkedList.traversal() // [0]
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
linkedList.traversal() // [0, 1, 2, 3]
linkedList.deleteByVal(3)
linkedList.traversal() // [0, 1, 2]
linkedList.deleteByVal(0)
linkedList.traversal() // [1, 2]
console.log(linkedList.deleteByVal(0)) // -1
linkedList.deleteByIndex(1)
linkedList.traversal() // [2]
linkedList.deleteByIndex(1)
linkedList.traversal() // []
console.log(linkedList.deleteByIndex(1)) // -1

这里主要实现了添加、删除、遍历的方法；在某索引前添加元素或者在某个值前添加的方法其实和删除节点差不多，有兴趣可以实现一下。我们可以注意到，这里我使用了 dummyHead ，这是一种技巧，处理头节点非常方便。后续例题讲解还会用到这个技巧。

双向链表

双向链表比单链表多个了 prev 指针，用于指向上一个节点。

这里给个双向链表的节点结构定义代码：

class DLinkedNode {
    constructor(val) {
        this.prev = null
        this.next = null
        this.val = val
    }
}

关于双向链表的创建以及添加元素方法实现，这里我们可以使用虚拟头节点和虚拟尾节点方便后续操作。

class DLinkedList {
    constructor() {
        this.dummyHead = new DLinkedListNode('head')
        this.dummyTail = new DLinkedListNode('tail')
        this.dummyHead.next = this.dummyTail
        this.dummyTail.prev = this.dummyHead
    }

    append(val) {
        const newNode = new DLinkedListNode(val)

        newNode.next = this.dummyTail
        newNode.prev = this.dummyTail.prev
        this.dummyTail.prev.next = newNode
        this.dummyTail.prev = newNode
    }

    traversal() {
        let p = this.dummyHead.next
        const res = []

        while (p && p.next) {
            res.push(p.val)
            p = p.next
        }

        console.log(res)
    }
}

const dLinkedList = new DLinkedList()
dLinkedList.append(1)
dLinkedList.append(2)
dLinkedList.append(3)
dLinkedList.append(4)
dLinkedList.append(5)
dLinkedList.traversal() // [ 1, 2, 3, 4, 5]

这里使用了虚拟尾节点之后，对于添加元素很方便，只要操作尾节点即可。

循环链表

循环链表就是最后一个节点指向头节点，这里暂时不做过多讲解。

接下来我们看几个题目：

例题

2. 两数相加

206. 反转链表

141. 环形链表

两数之和

var addTwoNumbers = function(l1, l2) {
    // dummyHead虚拟头节点，用于保存合并后的链表
    const dummyHead = new ListNode(0)
    // 当前处理的指针，每次通过curr.next构造新节点
    let curr = dummyHead, carry = 0

    while (l1 || l2 || carry > 0) {
        const val1 = l1 ? l1.val : 0
        const val2 = l2 ? l2.val : 0
        const sum = val1 + val2 + carry

        curr.next = new ListNode(sum % 10)
        carry = Math.floor(sum / 10)

        l1 = l1 && l1.next
        l2 = l2 && l2.next
        curr = curr.next
    }

    return dummyHead.next
};

其实这题相加操作有很多类似题，比如字符串相加，也就是大数相加。有兴趣可以去做做。这里主要多了链表指针的相关处理。

反转链表

这题我们可以使用双指针，prev 为上一个节点，curr 为当前节点；然后每次将 curr.next 设置为 prev；以此循环，则实现了链表的反转。具体代码实现如下:

var reverseList = function(head) {
    let prev = null, curr = head

    while (curr) {
    	// 需要保存 curr.next，不然进行不了下一步操作了
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }

    return prev
};

环形链表

这道题我们可以使用 Set 来解决，但是有另外一种更有意思的解法：快慢指针，快指针每次走两步，慢指针每次走一步，如果有环的话，快指针一定会追上慢指针。具体实现如下：

var hasCycle = function(head) {
    let fast = head, slow = head

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

        if (fast === slow) {
            return true
        }
    }

    return false
};

总结：链表操作其实将指针改来改去，我们要注意一些边界问题。同时注意利用虚拟节点，快慢指针等技巧优化代码。

leetcode题解github地址：https://github.com/webpig/leetcode，之后会继续整理更多题解。欢迎大家一起交流。