经典150题 - 链表

141. 环形链表

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

2. 两数相加

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode()
    let p1 = l1, p2 = l2, p3 = dummy
    let count = 0
 
    while(p1 || p2) {
        let temp = (p1?.val??0) + (p2?.val??0) + count
        p3.next = new ListNode(temp % 10)
        count = temp > 9 ? 1 : 0
        p1 = p1?.next
        p2 = p2?.next
        p3 = p3?.next
    }
    if(count) {
        p3.next = new ListNode(count)
    }
 
    return dummy.next
};

21. 合并两个有序链表

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

92. 反转链表 II

var reverseBetween = function(head, left, right) {
    if(left === right) return head
    let dummy = new ListNode(null, head)
    let past = dummy
 
    for(let i = 1; i < left; i++) {
        past = past.next
    }
    let current = past.next
    let prev = null
 
    for(let i = left; i<= right;i++) {
        let temp = current.next
        current.next = prev
        prev = current
        current = temp
    }
 
    past.next.next = current
    past.next = prev
 
    return dummy.next
};

19. 删除链表的倒数第 N 个结点

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(null, head)
    let fast = dummy
    let slow = dummy
 
    while(n) {
        fast = fast.next
        n--
    }
    while(fast?.next) {
        fast = fast.next
        slow = slow.next
    }
 
    slow.next = slow.next.next
 
    return dummy.next
};

82. 删除排序链表中的重复元素 II

var deleteDuplicates = function(head) {
    const dummy = new ListNode(null, head)
 
    let prev = dummy
    let cur = head
 
    while(cur) {
        if(cur.next && cur.val === cur.next.val) {
            while(cur.next && cur.val === cur.next.val) {
                cur = cur.next
            }
            prev.next = cur.next
        } else {
            prev = cur
        }
        cur = cur.next
    }
 
    return dummy.next
};

61. 旋转链表

var rotateRight = function(head, k) {
    if(!head || !k || !head.next) return head
 
    let len = 1, tail = head
    while(tail.next) {
        tail = tail.next
        len++
    }
    tail.next = head
 
    k = k%len
    if(!k) {
        tail.next = null
        return head
    }
 
    let newTail = head
    for(let i = 0; i < len-k-1;i++) {
        newTail = newTail.next
    }
    const newHead = newTail.next
    newTail.next = null
 
    return newHead
};

86. 分隔链表

var partition = function(head, x) {
    const beforeHead = new ListNode(null)
    const afterHead = new ListNode(null)
 
    let before = beforeHead
    let after = afterHead
 
    while(head) {
        if(head.val < x) {
            before.next = head
            before = before.next
        } else {
            after.next = head
            after = after.next
        }
        head = head.next
    }
 
    after.next = null
    before.next = afterHead.next
    return beforeHead.next
};

146. LRU 缓存

/**
 * @param {number} capacity
 */
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)
    }
};
 
/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

相关笔记

• 链表基础
• 链表专题
• GRD 链表刷题