Welcome to my blog

The structure of linked lists

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
    }
}
Copy the code

Common Topics

Reverse a linked list

Title source

1. The current node becomes the next node of the next node. 2. Next = cur.next cur.next = pre pre = cur = nextCopy the code

const reverseList = head= > {
    if (head == null || head.next == null) return head
    // If there is only one node left in the list, the list will fall back
    let p = reverseList(head.next)
    // The current node becomes the end of the queue
    head.next.next = head
    // Next for the current 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
}
Copy the code

Replication of complex linked lists

Title source

Idea 1: Create a new list with Next, and then map the new list to the old one. F (old[n]) = f(new[n]) = f(old[n]) = f(new[n]Copy the code

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

const copyRandomList = head= > {
    const map = new Map(a)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)
}

Copy the code

Merges two sorted lists

Title source

If both of them are in order, it is very easy to get themCopy the code

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
}
Copy the code

The KTH node from the bottom of the list

Title source

The classic two-pointer problemCopy the code

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

Copy the code

Draw the last number left in the circle

Title source

0->1->2->3->4 m = 2 1 3 4Copy the code

/ / will timeout
const lastRemaining1 = (n, m) = > {
    let start = 0
    let pre = null
    let head = null
    // create list ring
    while(start ! == n) {const node = newListNode(start) pre && (pre.next = node) ! pre && (head = node) pre = node start +=1
    }
    pre.next = head
    // Head === pre when only one node is left
    // count % m === 0
    let count = 0
    while(head ! == pre) { count +=1
        if (count % m === 0) {
            pre.next = head.next
        } else {
            pre = pre.next
        }
        head = head.next
    }
    return head.val
}
Copy the code

Circular linked list 1

Title source

Fast and slow pointer, can meet is the ringCopy the code

/ / will 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
}
Copy the code

Circular linked list 2

Title source

We need to use the set storage node, when there is a node in the next node in the set, it is a ringCopy the code

const detectCycle = function (head) {
    const set = new Set(a)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
}
Copy the code