Welcome to my blog

The structure of a linked list

function ListNode(val, next) { this.val = (val === undefined ? 0 : val) this.next = (next === undefined ? null : next) this.toString = () => { let stack = [this.val] let p = this.next while (p) { stack.push(p.val) p = p.next } return  stack } }

Common Topics

Reverse a linked list

Title source

> 1. The current node becomes the next node of the next node > 2. Next = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE PRE = PRE

Const reverseList = head = > {the if (head = = null | | head. The next = = null) return the head / / traversing the list only one node back later, Let p = reverseList(head.next) // The current node is the end of the queue head.next. Next = head // The next node is null head.next = null return p } const reverseList1 = head => { let cur = head, pre = null, next = null while (cur) { next = cur.next cur.next = pre pre = cur cur = next } return pre }

The replication of complex linked lists

Title source

Idea 1: create a new linked list with next, and then map the new linked list to the old one. F (old[n]) = f(new[n]) = f(new[n]

function Node(val, next, random) {
    this.val = val;
    this.next = next;
    this.random = random;
}

const copyRandomList = head => {
    const map = new Map()
    let p = head, pre = null
    // create new list and handle map for old list and new list
    while (p) {
        const node = new Node(p.val)
        map.set(p, node)
        pre && (pre.next = node)
        pre = node
        p = p.next
    }
    // log('new list', map.get(head))
    // traverse map
    for (let [oldNode, newNode] of map.entries()) {
        let key = oldNode.random
        let findNode = map.get(key)
        newNode.random = findNode
    }
    return map.get(head)
}

Merges two sorted linked lists

Title source

Idea: If both of them are in order, it is easy to get them. Let's go through them together and compare them once

const mergeTwoLists = (l1, l2) => { let pre = null let head = null while (l1 && l2) { const node = new ListNode(Math.min(l1.val, l2.val)) pre && (pre.next = node) ! pre && (head = node) pre = node l1.val < l2.val ? (l1 = l1.next) : (l2 = l2.next) } while (l1) { if (! pre) return l1 pre.next = l1 pre = pre.next l1 = l1.next } while (l2) { if (! pre) return l2 pre.next = l2 pre = pre.next l2 = l2.next } return head }

The KTH reciprocal node in the linked list

Title source

Idea: Classic double pointer problem

const getKthFromEnd = (head, k) => { let fast = head, Slow = head // while (k) {fast = fast.next k -= 1} // while (fast) {fast = fast.next slow = slow.next} return slow }

The last number left in the circle

Title source

0->1->2->3->4 m = 2 1 3 0 4

// timeout const lastRemaining1 = (n, + +); m) => { let start = 0 let pre = null let head = null // create list ring while (start ! == n) { const node = new ListNode(start) pre && (pre.next = node) ! Pre-&& (head = node) pre = node start += 1} pre-. next = head // Let count = 0 while (head! == pre // count % m === 0 == pre) { count += 1 if (count % m === 0) { pre.next = head.next } else { pre = pre.next } head = head.next } return head.val }

Ring list one

Title source

Thinking: fast and slow pointer, can meet is the ring

// timeout const hasCycle = function (head) {let result = false; if (! head) return result; let slow = head let quick = head.next while ((quick ! == slow)) { if (! quick || ! slow || ! quick.next) { return result; } slow = slow.next quick = quick.next.next } if (quick === slow) { result = true } return result }

Ring list two

Title source

Here, the fast and slow pointer needs to be analyzed mathematically. Generally speaking, it is more difficult to use the set storage node. When there is a node in the set, the next node in the set indicates that it is a ring

const detectCycle = function (head) { const set = new Set() let pos = null if (! head) return pos while (head) { if (set.has(head)) { pos = head break } else { set.add(head) } head = head.next } return  pos }