GRD 链表刷题

21. 合并两个有序链表

var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode()
    let p = dummy, p1 = list1, p2 = list2
    while(p1 && p2) {
        if(p1.val < p2.val) {
            p.next = p1
            p1 = p1.next
        } else {
            p.next = p2
            p2 = p2.next
        }
        p = p.next
    }
    p.next = p1 || p2
    return dummy.next
};

141. 环形链表

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

206. 反转链表

var reverseList = function(head) {
    let prev = null
    let curr = head
 
    while(curr) {
        let p = curr.next
        curr.next = prev
        prev = curr
        curr = p
    }
 
    return prev
};

876. 链表的中间结点

var middleNode = function(head) {
    const dummy = new ListNode(0, head)
    let fast = dummy, slow = dummy
    while(fast?.next?.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow.next
};

146. LRU 缓存

var LRUCache = function(capacity) {
    this.map = new Map()
    this.capacity = capacity
};
 
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(!this.map.has(key)) return -1
    let value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
};
 
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)) {
        this.map.delete(key)
    }
    this.map.set(key, value)
    if(this.map.size > this.capacity) {
        this.map.delete(this.map.keys().next().value)
    }
};

相关笔记

• 链表基础
• 链表题目（合并有序链表、LRU）
• 链表专题（反转、环形链表）