V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzzzzggggggg
V2EX  ›  程序员

[第 7 期] 盘点那些面试中会被问到的链表算法题

  •  1
     
  •   zzzzzzggggggg · 2020-04-06 10:25:03 +08:00 · 1861 次点击
    这是一个创建于 660 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这周盘点一下面试中最容易被问到的链表类算法题,可能下一次面试中就会出现这些题目和技巧哦。

    基础概念

    首先,链表是一种常见的数据结构,常见的有单链表、双向链表等等。
    拿单链表来举例,对于每一个节点可以使用下面的数据结构表示:

    struct ListNode {
      val: any; // 节点的值
      next: ListNode; // 该节点指向的下一个节点
    }
    

    下图可以简单的描述一个链表的结构 对于链表来说,一定要掌握的操作就是添加节点和删除节点,因为这是所有技巧的基础。

    删除节点

    如果要在下图中删除 2 这个节点,就可以进行如下操作:

    pre.next = cur.next;
    cur.next = null;
    

    因为需要遍历链表找到 pre 和 cur,所以删除操作的时间复杂度是 O(N),空间复杂度是 O(1)

    添加节点

    如果要在下图中添加 2 这个节点,就可以进行如下操作

    next = pre.next;
    pre.next = cur;
    cur.next = next;
    

    添加新节点的时间复杂度是 O(1),空间复杂度是 O(1)

    经典题目

    反转链表

    LeetCode.206 ,难度简单

    题目

    反转一个单链表。

    示例:

    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

    思路

    这道题目也算是链表类题目的老江湖了,印象中从校招一直考到社招,出现频率之高令人咋舌。
    对于例子1->2->3->4->5->NULL来说,遍历一遍链表,把每个节点的 next 属性指向它的前一个节点即可,如下图所示:

    对于每一个节点来说,需要知道它的前一个节点 pre 是谁,也需要知道它的下一个节点是谁(维持链表的遍历);下面我给出一个非递归的方法,当然也递归的方法,读者感兴趣可以自行实现一下。

    代码

    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function(head) {
        if(head === null || head.next === null)
          return head;
      
        let pre = null, cur = head;
        while(cur !== null) {
            const next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        return pre;
    };
    

    环形链表 II

    题目

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null 。

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    说明:不允许修改给定的链表。

    示例 1:

    输入:head = [3,2,0,-4], pos = 1
    输出:tail connects to node index 1
    解释:链表中有一个环,其尾部连接到第二个节点。

    示例 2:

    输入:head = [1,2], pos = 0
    输出:tail connects to node index 0
    解释:链表中有一个环,其尾部连接到第一个节点。

    示例 3:

    输入:head = [1], pos = -1
    输出:no cycle
    解释:链表中没有环。

    思路

    这也是一道经典的题目,可以使用快慢指针的办法来解决之,代码如下所示;
    那么为什么使用快慢指针就可以检测出链表是否有环并且找到第一个入环节点呢?证明如下:

    如图,设整个链表长度为 L,环长度为 R,且距离具有方向性,例如 CB 是 C 点到 B 点的距离,BC 是 B 点到 C 点的距离,CB!=BC 。当证明有环时,fast 和 slow 都顺时针到了 B 点,则此时:
    slow 走的距离:AC+CB
    fast 走的距离:AC+k*R+CB(k=0,1,2...)
    由于 fast 每次走 2 个节点,slow 每次走 1 个节点,所以:
    2(AC+CB) = AC+k*R+CB
    AC+CB = k*R
    AC+CB = (k-1)*R+R
    AC = (k-1)*R+R-CB
    AC = (k-1)*R+BC
    从最终的表达式可以看出来,AC 的距离等于绕环若干圈后再加上 BC 的距离,也就是说慢指针从 A 点出发以速度 1 前进、快指针从 B 点出发以速度 1 前进,则慢指针到 C 点时,快指针也必然到了。

    代码

    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var detectCycle = function(pHead) {
        if(pHead === null || pHead.next === null || pHead.next.next === null)
            return null;
        var fast = pHead;
        var slow = pHead;
    
        while(fast.next !==null && fast.next.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow === fast)
                break;
        }
    
        if(fast === null || fast.next === null || fast.next.next === null)
            return null;
        // 有环,slow 重新回到链表头
        slow = pHead;
        
        // slow 和 fast 重新相遇时,相遇节点就是入环节点
        while(slow !== fast) {
            slow = slow.next;
            fast = fast.next;
        }
    
        return slow;
    };
    

    奇偶链表

    LeetCode.328 ,难度中等

    题目

    给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

    请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

    示例 1:

    输入: 1->2->3->4->5->NULL
    输出: 1->3->5->2->4->NULL

    示例 2:

    输入: 2->1->3->5->6->4->7->NULL
    输出: 2->3->6->7->1->5->4->NULL

    说明:
    应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

    思路

    之前说过,增删节点是链表的重要基础技巧,本道题就体现的很深刻。
    从题意得知,奇数节点都在前面,偶数节点都在后面,即把1->2->3->4->5->NULL变成1->3->5->2->4->NULL,如下图所示:

    可以看到问题的关键是奇数节点和偶数节点交替抽出成两条独立的链表,最终再合成一条新的链表。

    代码

    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var oddEvenList = function(head) {
        if(head === null || head.next === null || head.next.next === null)
            return head;
        
        let cur1 = head, cur2 = head.next;
        let evenHead = head.next;
        while(cur1.next && cur2.next) {
            cur1.next = cur2.next;
            cur1 = cur1.next;
            cur2.next = cur1.next;
            cur2 = cur2.next;
        }
        cur1.next = evenHead;
        
        return head;
    };
    

    欢迎关注前端亚古兽( fe-yagushou ),更多前端以及互联网周边知识推送。

    9 条回复    2020-04-07 17:23:55 +08:00
    felix021
        1
    felix021  
       2020-04-06 11:59:33 +08:00
    我就想知道这个图是咋贴的。。
    ufan0
        2
    ufan0  
       2020-04-06 12:44:38 +08:00 via Android   ❤️ 1
    @felix021 贴图吗?

    首先你需要找到一个可以正常使用的图床,上传图片获得直链后直接复制过来就好了。
    zzzzzzggggggg
        3
    zzzzzzggggggg  
    OP
       2020-04-06 13:24:01 +08:00   ❤️ 1
    @felix021 找个放图片的地方就行了
    zzzzzzggggggg
        4
    zzzzzzggggggg  
    OP
       2020-04-06 13:24:33 +08:00
    为啥收藏这么多,多少来句评论给点互动啊😅
    felix021
        5
    felix021  
       2020-04-06 13:44:40 +08:00
    @zzzzzzggggggg 哈哈哈 我那篇也是这样,勉强用“曲高和寡”自我安慰下。

    另外贴图这个,我用我自己网站的图片 url,貌似 v2 不认,你这是用的哪家图床呢?
    also24
        6
    also24  
       2020-04-06 16:29:23 +08:00   ❤️ 1
    @felix021 #5
    主贴中贴图不区分图床,正常使用 markdown 语法即可
    zzzzzzggggggg
        7
    zzzzzzggggggg  
    OP
       2020-04-06 18:27:14 +08:00
    @felix021 就随便哪一家都行,应该不牵扯😅
    OxO
        8
    OxO  
       2020-04-07 17:09:31 +08:00
    进来
    哇,这么长
    拉到下面
    点击收藏
    返回到首页
    搞定
    zzzzzzggggggg
        9
    zzzzzzggggggg  
    OP
       2020-04-07 17:23:55 +08:00
    @OxO 哈哈哈,我感觉你说出了所有收藏者的心声
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3106 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 05:03 · PVG 13:03 · LAX 21:03 · JFK 00:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.