likes
comments
collection
share

剑指 Offer（专项突击版）第23|24题

作者站长头像
站长
· 阅读数 42

前言

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

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

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

难度：简单

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

剑指 Offer（专项突击版）第23|24题

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

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

示例 1：

剑指 Offer（专项突击版）第23|24题

输入：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：

剑指 Offer（专项突击版）第23|24题

输入：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：

剑指 Offer（专项突击版）第23|24题

输入：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。

剑指 Offer（专项突击版）第23|24题

/**
 * 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节点

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

剑指 Offer（专项突击版）第23|24题

/**
 * 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向后移一位。

剑指 Offer（专项突击版）第23|24题

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

剑指 Offer（专项突击版）第23|24题

传送门

转载自:https://juejin.cn/post/7184790760397471803
评论
请登录