打印两个链表的第一个公共节点

不作声

发布于 2020-12-21 14:17:05

8350

发布于 2020-12-21 14:17:05

文章被收录于专栏：M不作声

「力扣上剑指offer52，打印两个链表的第一个公共节点。」

举个栗子

很多问题都有多种算法可以解决。

暴力解题

最最最简单的就是暴力解题，你说两个链表的第一个公共节点，那好，我就挨个遍历就完事了。

对于A链表中的每个节点，都遍历B链表，如果有相同的节点，则返回该节点。

代码就不写了，毕竟没人会看效率最低的代码。

「假设链表A长度为n，链表B长度为m，时间复杂度大约为O(nm)，空间复杂度O(1)。」

还有一种是借助额外的空间，使用两个栈。将两个链表中的节点全都入栈，判断两个栈顶元素，如果相同则出栈；如果不同则返回刚出栈的元素。

「时间复杂度为O(n+m)，空间复杂度(n+m)」

快慢指针和双指针

快慢指针是两个指针，先让快指针走一段距离，然后快慢指针以同样的速度走。

题目没有实现直接获取链表长度的方法，所以需要先遍历分别遍历两个链表一次，才能知道哪个链表长。之后再进行实际的快慢指针。

这里我们可以先做一个互补操作，使两个链表长度相等，但实际上我们不需要生成如下的链表，只需要遍历完一条链表后指向另一条链表的表头即可。

链表互补

链表互补之后，链表长度相等，双指针同时前进直接遍历。如果最后有相同部分，说明两个链表相交，如果没有相同部分，则说明两个链表没有交点，返回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 || headB) {
    return null;
  }
  
  let h1 = headA;
  let h2 = headB;

  while (h1 !== h2) {
    h1 = h1 == null ? h2 : h1.next;
    h2 = h2 == null ? h1 : h2.next;
  }
  
  return h1;
};

这样下来时间复杂度为O(n+m)，空间复杂度O(1)

使用map

map是ES6的数据结构，可以保存键值对。

我们遍历一条链表，将所有的节点的值都设为true，然后遍历另一条链表，访问map对象，判断map中是否存在该节点。

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    const map = new Map();
    let h1 = headA
    while (h1) {
        map.set(h1, true);
        h1 = h1.next;
    }

    let h2 = headB
    while (h2) {
        if (map.has(h2)) return h2;
        h2 = h2.next;
    }
  
    return null;
};

这个算法需要先创建一个map对象，存放n个节点，空间复杂度是O(n)。

向map中添加添加元素需要遍历一次链表a，然后再遍历链表b判断是否存在该节点，时间复杂度是O(n+m)。

总结

最优解是双指针解法，时间复杂度为O(N)级，空间复杂度为O(1)常数级。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自大前端合集微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度