“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

define

What is a linked list? Linked lists represent data structures that use Pointers to concatenate a series of discrete chunks of memory.

There is no definition of a linked list in JS, and there is no definition of a pointer. We can think of Pointers as references.

There are three commonly used linked lists: single linked list, bidirectional linked list, circular linked list.

Specific definition we do not repeat, a lot of online information, let’s do the problem directly ~

How to implement a linked list

let data = [];
let next = [];

function add(cur, p, v) {
    next[p] = next[cur]
    next[cur] = p;
    data[p] = v;
}

function main() {
    const head = 100;
    add(head, 1.10)
    add(1.2.20)
    add(2.3.30)
    add(3.4.40)

    add(2.5.50)
    data[head] = 1
    let p = head;
    while(p) {
        console.log('- >', data[p])
        p = next[p]
    }
}

main()
Copy the code

Algorithm problem

Print the linked list from end to end

The simplest way is to stuff the list data into an array with unshift().

I’m going to flip the list first (just to try flipping the list incidentally)

var reversePrint = function(head) {
    const arr = [];
    let dump = null;
    let curIdx = head;
    while(curIdx) {
        const next = curIdx.next;
        curIdx.next = dump;
        dump = curIdx;
        curIdx = next;
    }
    let idx = dump;
    while(idx) {
        arr.push(idx.val)
        idx = idx.next;
    }
    return arr
};
Copy the code

Interview question 02.02. Return the last KTH node

When the fast pointer points to null, the value that the slow pointer points to is the desired value

var kthToLast = function(head, k) {
    let slow = head, fast = head;
    while(k) {
        fast = fast.next;
        k--;
    }
    while(fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow.val;
};
Copy the code

141. Circular linked lists

Fast and slow pointer search, fast pointer every two steps, slow pointer every step, if there is a ring, must intersect, otherwise will traverse the linked list.

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

Interview question 02.07. Linked lists intersect

If two lists intersect, A will start at the head of B, and B will start at the head of A, and they must meet at the intersection. A + b + c = a + b + c.

If they don’t intersect, a plus b is equal to b plus a, there’s no common C, both sides point to null.

The condition for breaking out of the loop is that the two nodes are equal, that is, they meet or do not intersect each other once a, B.

Note that you must go down the null node, otherwise two linked lists that do not intersect will never be equal and enter an infinite loop.

var getIntersectionNode = function(headA, headB) {
    let l = headA, r = headB;
    while(l ! == r) { l = l ? l.next : headB; r = r ? r.next : headA; }return l;
};
Copy the code