前端常见算法题(链表篇)

作者: 维李设论 | 来源:发表于2021-08-10 23:27 被阅读0次

前端常见算法题(链表篇)
前端常见算法题(数组篇)
前端常见算法题(树篇)
数据结构 - 单向链表及相关算法
前端常见算法题(动态规划篇)
程序员进阶之算法练习：LeetCode专场
程序员进阶之算法练习（三十五）LeetCode专场
单链表算法题整理（思路详解）
iOS面试题之人在面试都是套路（十二）*宇*天公司iOS面试题
前端校招准备系列--js实现链表的基本操作

前端 | 前端常见算法题(链表篇).png

一、反转问题

2021.02.11

No.25 K个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方案一：

/*
 * @lc app=leetcode.cn id=25 lang=javascript
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * 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 reverseKGroup = function(head, k) {
    // 链表转数组
    const  list2Arr = head => {
        const a = [head.val];
        while(head.next) {a.push(head.next.val);head = head.next;}
        return a;
    }
    // 数组转链表
    const arr2List = arr => {
        let head = new ListNode(arr[0]);
        let cur = head;
        for(let i=1; i < arr.length; i++) {
            cur.next = new ListNode(arr[I]);
            cur = cur.next;
        };
        return head;
    };
    // 对k个节点进行数组切割即可
    const kReverse = (a,k) => {
        const r = [];
        let cnt = 0;
        while(a.length >= k + cnt)
        {
            let tmp = a.slice(cnt, cnt+k);
            tmp.reverse();
            tmp.map( (x)=> r.push(x));
            cnt += k;
        }
        a.slice(cnt).map( (x)=> r.push(x));
        return r;
    }
    
    return arr2List(kReverse(list2Arr(head), k));
};

方案二：

/*
 * @lc app=leetcode.cn id=25 lang=javascript
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * 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 reverseKGroup = function(head, k) {
    let cur = head;
    let count = 0;
    // 求k个待反转元素的首节点和尾节点
    while(cur != null && count != k){
        cur = cur.next;
        count++;
    }
    // 足够k个节点，去反转
    if(count == k){
        // 递归链接后续k个反转的链表头节点
        cur = reverseKGroup(cur,k);
        while(count != 0){
            count--;
            // 反转链表
            let tmp = head.next;
            head.next = cur;
            cur = head;
            head = tmp;
        }
        head = cur;
    }
    return head;
};

方案三：

/*
 * @lc app=leetcode.cn id=25 lang=javascript
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * 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 reverseKGroup = function(head, k) {
    if(!head) return null;
    // 反转链表
    let reverse = (a,b) => {
        let pre;
        let cur = a;
        let next = b;
        while(cur != b){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    // 反转区间a-b的k个待反转的元素
    let a = head;
    let b = head;
    for(let i = 0;i < k;i++){
        // 不足k个，不需要反转
        if(!b) return head;
        b = b.next;
    }
    // 反转前k个元素
    let newHead = reverse(a,b);
    // 递归链接后续反转链表
    a.next = reverseKGroup(b,k);
    return newHead;
};

方案四：

/*
 * @lc app=leetcode.cn id=25 lang=javascript
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * 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 reverseKGroup = function(head, k) {
    let stack = [];
    let preHead = new ListNode(0);
    let pre = preHead;
    // 循环链接后续反转链表
    while(true){
        let count = 0;
        let tmp = head;
        while(tmp && count < k){
            stack.push(tmp);
            tmp = tmp.next;
            count++;
        }
        // 不够k个，直接链接剩下链表返回
        if(count != k){
            pre.next = head;
            break;
        }
        // 出栈即是反转
        while(stack.length > 0){
            pre.next = stack.pop();
            pre = pre.next;
        }
        pre.next = tmp;
        head = tmp;
    }
    return preHead.next;
};

方案五：

/*
 * @lc app=leetcode.cn id=25 lang=javascript
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * 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 reverseKGroup = function(head, k) {
    const myReverse = (head, tail) => {
        let prev = tail.next;
        let p = head;
        while (prev !== tail) {
            const nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return [tail, head];
    }
    const hair = new ListNode(0);
    hair.next = head;
    let pre = hair;

    while (head) {
        let tail = pre;
        // 查看剩余部分长度是否大于等于 k
        for (let i = 0; i < k; ++i) {
            tail = tail.next;
            if (!tail) {
                return hair.next;
            }
        }
        const nex = tail.next;
        [head, tail] = myReverse(head, tail);
        // 把子链表重新接回原链表
        pre.next = head;
        tail.next = nex;
        pre = tail;
        head = tail.next;
    }
    return hair.next;
};

有五种解法：1、利用数组求解，比较笨重，需要切换成数组再切回来；2、递归相关方案，利用栈、迭代等进行解析；3、利用虚置前节点，将复杂度降到常数级别，很巧妙

2021.02.12

No.61 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方案一：

/*
 * @lc app=leetcode.cn id=61 lang=javascript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * 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 rotateRight = function(head, k) {
    // 链表转数组
    const  list2Arr = head => {
        if(!head) return [];
        const a = [head.val];
        while(head.next) {a.push(head.next.val);head = head.next;}
        return a;
    }
    // 数组转链表
    const arr2List = arr => {
        if(arr.length == 0) return null;
        let head = new ListNode(arr[0]);
        let cur = head;
        for(let i=1; i < arr.length; i++) {
            cur.next = new ListNode(arr[I]);
            cur = cur.next;
        };
        return head;
    };
    // 数组位置变化
    const arrRotate = (a, k) => {
        const len = a.length;
        const hashTable = {};
        for(let i=0; i< a.length; i++) {
            hashTable[(i+k) % len] = a[i]
        };
        return Object.values(hashTable) 
    };
    return arr2List(arrRotate(list2Arr(head), k));
};

方案二：

/*
 * @lc app=leetcode.cn id=61 lang=javascript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * 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 rotateRight = function (head, k) {
    if (!head || k === 0) return head;  // 特判
    let p = head, len = 1;
    while (p.next) {
        p = p.next;
        len++;
    }
    p.next = head; // 首尾相接
    k = len - k % len; // 处理要移动的距离
    while (k--) p = p.next;
    head = p.next;  // head 指向第 len - k + 1 个节点，即答案
    p.next = null;  // 切断 len - k 与 len - k + 1 的关系
    return head;
}

方案三：

/*
 * @lc app=leetcode.cn id=61 lang=javascript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * 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 rotateRight = function(head, k) {
    if(head===null||head.next===null)return head;
    let len = 0;//链表长度
    let p = head;
    let first = head;//第一个结点
    let stack = [];//辅助栈
    while(p){
        stack.push(p);
        p = p.next;
        len++;
    }
    p = stack.pop();
    for(let i = 1;i<=k%len;i++){
        p.next = first;
        stack.unshift(p);
        first = p;
        p = stack.pop();
        p.next = null;
    }
    return first;
};

方案四：

/*
 * @lc app=leetcode.cn id=61 lang=javascript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * 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 rotateRight = function(head, k) {
       var order = new ListNode(0,head); // head链表的copy
       var fast = new ListNode(0,head); // 快指针
       var slow = new ListNode(0,head); // 慢指针
       var count = 0; // 链表长度
   
       while(order && order.next){ // 循环求链表长度
           order = order.next;
           count ++;
       }
       var n = k % count; // 因为 k > 链表长度 时，出现重复操作。对 k 求余,去除重复
   
       for (var i = 0; i < n; i++){ // 快指针先走 n 步
           fast = fast.next;
       }
       while(fast && fast.next){ // 链表的快指针、慢指针操作
           fast = fast.next;
           slow = slow.next;
       }
       
       // 两步操作
       // 第一、将倒数第 k%count 元素 与 倒数第 (k%count-1) 元素 断开
       var resultPre = slow.next; // 序号2  返回结果集的 起始位置
       var result = resultPre; // 序号3  最后return的结果集
       slow.next = null; // 将链表断开
       // 第二、再讲链表的尾部与头部链接
       while(resultPre && resultPre.next) {
           resultPre = resultPre.next
       }
       if (resultPre){ 
           resultPre.next = head; // 情况1：旋转链表后有改变，将链表拼接起来 
       }
       else {
           result = head;  // 情况2: 旋转链表后没有改变，返回原始链表
       }
       return result;
   };

方案五：

/*
 * @lc app=leetcode.cn id=61 lang=javascript
 *
 * [61] 旋转链表
 */

// @lc code=start
/**
 * 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}
 */
const rotateRight = (head, k) => {
    if (!head || !head.next) return head
    let curr = head, n = 0
    // 遍历链表计算其长度
    while (++n && curr.next) curr = curr.next
    k = k % n   // 去重
    // 链表右移
    while (k--) {
        curr = head
        while (curr.next.next) curr = curr.next
        // 这里curr是链表的打断位置，即倒数第二项
        curr.next.next = head // 链表最后一项指向头部形成环
        head = curr.next // 定位新的头节点
        curr.next = null // 打断链表环
    }
    return head
}

本题有五种思路：1、hash表存储，利用数组的位置排序进行hash敛散生成新的链表；2、链表成环，对应位置剪开；3、堆栈辅助处理循环剪断位置；4、快慢指针，根据双指针的位置间距进行处理，对新剪开位置使用另外两个指针记录处理；5、常规穷举，一步一步进行

2021.02.13

No.92 翻转链表-ii

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方案一：

/*
 * @lc app=leetcode.cn id=92 lang=javascript
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * 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} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    // 链表转数组
    const  list2Arr = head => {
        if(!head) return [];
        const a = [head.val];
        while(head.next) {a.push(head.next.val);head = head.next;}
        return a;
    }
    // 数组转链表
    const arr2List = arr => {
        if(arr.length == 0) return null;
        let head = new ListNode(arr[0]);
        let cur = head;
        for(let i=1; i < arr.length; i++) {
            cur.next = new ListNode(arr[I]);
            cur = cur.next;
        };
        return head;
    };
    // 数组 m => n 翻转
    const reversePosition = (a, m, n) => {
        return [...a.slice(0,m-1), ...a.slice(m-1,n).reverse(), ...a.slice(n)]
    };
    return arr2List(reversePosition(list2Arr(head),m,n));
};

方案二：

/*
 * @lc app=leetcode.cn id=92 lang=javascript
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * 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} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    // step1 => 双指针p1,p2保持固定间距
    const dummyHead = new ListNode(0, head);
    let p1 = p2 = head;
    let step2 = n - m;
    while (step2-- > 0) {
        p2 = p2.next;
    }
    let step1 = m - 1;
    let tmpHead = p1;
    while (step1-- > 0) {
        tmpHead = p1;
        p1 = p1.next;
        p2 = p2.next;
    }
    // step2 => 极其重要的测试case：p1指针压根没动【dummyHead就起作用了】
    if (p1 == head) {
        tmpHead = dummyHead;
    }
    // step3 => 尾插法
    let tmp = p1;
    while (tmp != p2) {
        tmp = p1.next;
        p1.next = tmp.next;
        tmp.next = tmpHead.next;
        tmpHead.next = tmp;
    }
    return dummyHead.next;
};

两种解法：1、转成数组，利用数组的slice及reverse拼接；2、双指针+尾插法，利用头尾指针的交换

2021.02.14

No.206 反转链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

方案一：

/*
 * @lc app=leetcode.cn id=206 lang=javascript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * 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 reverseList = function(head) {
    // 链表转数组
    const  list2Arr = head => {
        if(!head) return [];
        const a = [head.val];
        while(head.next) {a.push(head.next.val);head = head.next;}
        return a;
    }
    // 数组转链表
    const arr2List = arr => {
        if(arr.length == 0) return null;
        let head = new ListNode(arr[0]);
        let cur = head;
        for(let i=1; i < arr.length; i++) {
            cur.next = new ListNode(arr[I]);
            cur = cur.next;
        };
        return head;
    };
    // 数组 m => n 翻转
    const reverseList = (a) => {
        return a.reverse()
    };
    return arr2List(reverseList(list2Arr(head)));
};

方案二：

/*
 * @lc app=leetcode.cn id=206 lang=javascript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * 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 reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

方案三：

/*
 * @lc app=leetcode.cn id=206 lang=javascript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * 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 reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    }
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

三种方法：1、转成数组，利用数组的reverse；2、迭代；3.递归

总结：

反转链表问题常见的利用链表的三指针进行相关的反转，常见的为头指针、尾指针及替换指针的相关变形，可以利用栈等数据结构进行迭代或递归；

对于反转问题有一个取巧的办法就是将其转成数组后利用数组的相关api进行处理，再将数组转为链表

二、分隔合并

2021.02.18

No.21 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

image

前端常见算法题(链表篇)
一、反转问题 2021.02.11 No.25 K个一组翻转链表给你一个链表，每 k 个节点一组进行翻转，请你返...
前端常见算法题(数组篇)
一、和问题 2020.09.21 No.1 两数之和给定一个整数数组 nums 和一个目标值 target，请你...
前端常见算法题(树篇)
一、遍历问题 2020.11.02 No.94 二叉树的中序遍历给定一个二叉树，返回它的中序遍历。示例: 输...
数据结构 - 单向链表及相关算法
单向链表链表常见算法链表反转
前端常见算法题(动态规划篇)
一、路径问题 2021.05.13 No.514 自由之路电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为...
程序员进阶之算法练习：LeetCode专场
前言 LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题：题目1是基于链表的大数加法，既...
程序员进阶之算法练习（三十五）LeetCode专场
前言 LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题：题目1是基于链表的大数加法，既...
单链表算法题整理（思路详解）
前一篇文章中记录了单链表的实现和基本操作，在此基础上，本次整理了单链表的相关常见算法题的思路和C语言实现，留作复习...
iOS面试题之人在面试都是套路（十二）*宇*天公司iOS面试题
看来我还是学艺不精，上一篇文章刚总结常见的iOS笔试题算法，马上就遇到一家这样的考算法的公司，由于我链表的题没写出...
前端校招准备系列--js实现链表的基本操作
自己总结了一下链表的基本操作的实现，文末还有几道简单的算法题可供练习！前端校招准备系列--使用js实现链表的操作...