链表

链表

单向链表

// 单向链表节点类
Class Node() {
    constructor(val) {
        this.val = val;
        this.next = null
    }
}

// 单向链表类
Class ListNode() {
    constructor() {
        this.head = null;
        this.tail = null;
    }
}

双向链表

Class Node() {
    constructor(val) {
        this.prev = null;
        this.val = val;
        this.next = null;
    }
}

Class DoubleNode() {
    constructor() {
        this.head = null;
        this.tail = null;
    }
    // 末尾添加元素
    add(item) {
        let node = new Node(item);
        if (!head) {
            this.head = node;
            this.tail = node;
        } else {
            node.prev = this.tail;
            this.tail.next = node;
            this.tail = node;
        }
    }
    // 在某个位置添加元素
    addAt(index, item) {
        let cur = this.head;
        let node = new Node(item);
        // 如果在头部插入
        if(index === 0) {
            node.next = cur;
            cur.prev = node;
            this.head = node;
        } else {
            // 从第一个元素开始加
            let counter = 1;
            while(cur) {
                cur = cur.next;
                if (index === counter) {
                    node.prev = cur.prev;
                    node.next = cur;
                    cur.prev.next = node;
                    cur.prev = node;
                }
                counter++;
            }
        }
    }
    // 删除一个元素
    remove(item) {
        let cur = this.head
        while(cur) {
            // 找到了目标节点
            if(cur === item) {
                // 只有一个元素
                if (cur === this.head && cur === this.tail) {
                    this.head = null
                    this.tail = null
                // 目标为链头
                } else if (cur === this.head) {
                    this.head = this.head.next
                    this.head.prev = null
                } else if (cur === this.tail) {
                    this.tail = this.tail.prev
                    this.tail.next = null
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next
        }
    }
    // 在某个位置中删除元素
    removeAt(index) {
        let cur = this.head
        let counter = 1;
        // 删除链头
        if (index === 0) {
            this.head = this.head.next
            this.head.prev = null
        } else {
            while(cur) {
                cur = cur.next
                if(index === counter) {
                    // 如果在链尾
                    if(cur === this.tail) {
                        this.tail = this.tail.prev
                        this.tail.next = null
                    } else {
                        cur.prev.next = cur.next
                        cur.next.prev = cur.prev
                        break;
                    }
                }
                counter++
            }
        }
    }
    // 翻转链表
    reverse() {
        let cur = this.head
        let prev = null
        while(cur) {
            let next = cur.next
            // 交换指针
            cur.next = prev
            cur.prev = next
            // 向后移动
            prev = cur
            cur = next
        }
        // 当前末尾是prev
        this.tail = this.head
        this.head = prev
    }
    // 交换两个链表元素的位置
    swap(index1, index2) {
        if (index1 > index2) return swap(index2, index1)
        let cur = this.head
        let counter = 0;
        let firstNode
        while (cur!== null) {
            // 找到第一个
            if(counter === index1) {
                firstNode = cur
            // 找到第二个    
            } else (counter === index2) {
                let temp = firstNode.val
                firstNode.val = cur.val
                cur.val = temp
            }
            cur = cur.next
            counter++
        }
        return true
    }
    // 判断是否为空
    isEmpty() {
        return this.length() < 1;
    }
    // 查询链表长度
    length() {
        let cur = this.head;
        let counter = 0;
        while(cur !== null) {
            counter++;
            cur = cur.next;
        }
        return counter;
    }
    // 遍历链表
    traverse(fn) {
        let cur = this.head
        while(cur !== null) {
            fn(cur)
            cur = cur.next
        }
        return true
    }
    // 找到某个节点的索引
    find(item) {
        let cur = this.head
        let counter = 0
        while(cur !== null) {
            if（cur.val === item) {
                return counter
            }
            cur = cur.next
            counter++
        }
        return false;
    }
}

延伸题目

• 2.两数相加问题：题解

• 65.二进制求和：题解

• 371.两整数之和：题解

• 989.数组形式的整数加法：题解

• 237.删除链表中的节点：题解

• 203.移除链表元素：题解

• 206.反转链表：题解

• 剑指Offer 06. 从尾到头打印链表：题解

• 剑指Offer 18. 删除链表的节点：题解

• 剑指Offer 24. 反转链表：题解