剑指 Offer(专项突击版)第23|24题


theme: fancy

前言

  • 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer(专项突击版)》第23|24题。

剑指 Offer II 023. 两个链表的第一个重合节点

给定两个单链表的头节点 headA 和 headB ,请找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

难度:简单

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 
输出:Intersected at '8' 
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 
输出:Intersected at '2' 
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。 在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。 

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 
输出:null 
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。 由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。 这两个链表不相交,因此返回 null 。

知识点: 哈希表 链表 双指针

方法一:双指针

只有当链表 headA 和 headB 都不为空时,两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空,如果其中至少有一个链表为空,则两个链表一定不相交,返回 null。

当链表 headA 和 headB 都不为空时,创建两个指针 pA 和 pB,初始时分别指向两个链表的头节点 headA 和 headB,然后将两个指针依次遍历两个链表的每个节点。

具体做法如下:

每步操作需要同时更新指针 pA 和 pB。

如果指针 pA 不为空,则将指针 pA 移到下一个节点;如果指针 pB 不为空,则将指针 pB 移到下一个节点。

如果指针 pA 为空,则将指针 pA 移到链表 headB 的头节点;如果指针 pB 为空,则将指针 pB 移到链表 headA 的头节点。

当指针 pA 和 pB 指向同一个节点或者都为空时,返回它们指向的节点或者 null。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) return null;

    let pA = headA, pB = headB;

    while (pA !== pB) {
        // 链表A循环结束就循环链表B 
        pA = pA === null ? headB : pA.next;
        // 链表B循环结束就循环链表A 
        pB = pB === null ? headA : pB.next;
    }

    // 当pA == pB时就是交点
    return pA;
};

复杂度分析

  • 时间复杂度:O(m+n),其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表,每个指针遍历两个链表各一次。
  • 空间复杂度:O(1)。

剑指 Offer II 024. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

难度:简单

示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]

方法一:迭代法

链表与数组的不同在于没有索引,不能通过下标获取当前值,所以需要一个节点一个节点进行反转。

在遍历链表时,将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存

储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

关键步骤:

  1. 存储原本的next节点
  2. 将当前next指向前一个节点
  3. 将前一个节点指向当前节点
  4. 将当前节点指向存储的next节点

(如果有点饶,可以画图,多想多记)

/**
 * 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 preHead = null;
    let cur = head;
    while (cur !== null) {
        let next = cur.next;
        cur.next = preHead;
        preHead = cur;
        cur = next;
    }
    return preHead;
};

复杂度分析

  • 时间复杂度:O(n),其中 n** 是链表的长度。需要遍历链表一次。
  • 空间复杂度:O(1)。

方法二:头插法

思路:准备一个临时节点,然后遍历链表,准备两个指针head和next,每次循环到一个节点的时候,将

head.next指向temp.next,并且将temp.next指向head,head和next向后移一位。

var reverseList = function (head) {
  let temp = new ListNode();
  let next = null;
  while (head) {
    next = head.next;//下一个节点
    head.next = temp.next;
    temp.next = head;//head接在temp的后面
    head = next;//head向后移动一位
  }
  return temp.next;
};

复杂度分析:

  • 时间复杂度:O(n), n为链表节点数
  • 空间复杂度:O(1)

方法三:递归

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;
};

复杂度分析

  • 时间复杂度:O(n),假设 n 是列表的长度,那么时间复杂度为 O(n)。
  • 空间复杂度:O(n),由于使用递归,将会使用隐式栈空间。递归深度可能会达到 n 层。

so

  • 结尾依旧:长风破浪会有时,直挂云帆济沧海!
  • 在线整理的确实很好,对掘金的文章进行了一个汇总整理,在线刷题指南,拿走不谢,要学会站在别人的肩膀上提升自己点击这里–>  前端进阶指南

image.png

传送门

© 版权声明
THE END
喜欢就支持一下吧
点赞5 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容