链表

链表

链表是面试算法中比较常见的一种，这里根据灵神的算法题单做了一些链表的题目

§1.1 遍历链表

1290. 二进制链表转整数

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number}
 */
var getDecimalValue = function(head) {
    let ans=0;
    for(let cur=head;cur;cur=cur.next)
    {
        ans*=2;
        ans+=cur.val;
    }
    return ans;
};

2058. 找出临界点之间的最小和最大距离

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nodesBetweenCriticalPoints = function (head) {
    let pre = head;
    let cur = pre.next;
    let nxt = cur.next;
    const flag = [];
    let index = 1;
    while (nxt) {
        if (cur.val < nxt.val && cur.val < pre.val)
            flag.push(index);
        if (cur.val > nxt.val && cur.val > pre.val)
            flag.push(index);
        index++;
        pre = cur;
        cur = nxt;
        nxt = nxt.next;

    }
    if (flag.length < 2) {
        return [-1, -1];
    }
    let min = Infinity;
    let max = flag[flag.length - 1] - flag[0];
    for (let i = 1; i < flag.length; i++) {
        min = Math.min(flag[i] - flag[i - 1], min);
        max = Math.max(flag[i] - flag[i - 1], max);
    }
    return [min, max];
};

2181. 合并零之间的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var mergeNodes = function (head) {
    let start = head;
    for (let cur = head.next; cur.next; cur = cur.next) {
        if (cur.val) {
            start.val += cur.val;
        }
        else {
            start = start.next;
            start.val = 0;
        }
    }
    start.next = null;
    return head;
};

725. 分隔链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function (head, k) {
    let cnt = 0;
    for (let cur = head; cur; cur = cur.next) {
        cnt++;
    }
    const divide = Math.floor(cnt / k);
    let left = cnt - divide * k;
    let ans = new Array(k).fill(null);
    let now = head;
    for (let i = 0; i < k && now; i++) {
        ans[i] = now;
        let size = divide + (left !== 0 ? 1 : 0);
        for (let j = 1; j < size; j++) {
            now = now.next;
        }
        if (left > 0) left--;
        if (now) {
            const nxt = now.next;
            now.next = null;
            now = nxt;
        }
    }
    return ans;
};

817. 链表组件

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number[]} nums
 * @return {number}
 */
var numComponents = function (head, nums) {
    const set = new Set();
    for (const num of nums)
        set.add(num);
    let flag = false;
    let cnt = 0;
    for (let cur = head; cur; cur = cur.next) {
        if (set.has(cur.val)) {
            if (!flag) {
                cnt++;
                flag = true;
            }

        } else {
            flag = false;
        }
    }
    return cnt;
};

§1.4 反转链表

2074. 反转偶数长度组的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseEvenLengthGroups = function (head) {
    let size = 1;
    let node = [];
    let cur = head;
    while (cur !== null) {
        node.push(cur);
        if (node.length === size || cur.next === null) {
            let n = node.length;
            if (n % 2 === 0) {
                for (let i = 0; i < Math.floor(n / 2); i++) {
                    let temp = node[i].val;
                    node[i].val = node[n - 1 - i].val;
                    node[n - 1 - i].val = temp;
                }
            }
            node = [];
            size++;
        }
        cur = cur.next;
    }
    return head;
};