LeetCode 剑指 Offer 52. 两个链表的第一个公共节点 （虐狗指针法+朴素可怜法）（JavaScript数据结构-链表）

题链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

---

题描述：

---

解题思路：

第一种方法：浪漫指针法

使用两个指针 tempA，tempB 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 tempA 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点，当 tempB 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。 它们相遇时所指向的结点就是第一个公共结点。

/** * 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) { let tempA = headA; let tempB = headB; while (tempA != tempB ) { tempA = (tempA != null)? tempA.next : headB; tempB = (tempB != null)? tempB.next : headA; } return tempA; };

设两条链表长度分别为 m，n：

时间复杂度：O(m+n)；

空间复杂度：O(1)；

 

第二种方法：凄凉朴素可怜法

遍历两个链表，链表长度较长的指针移动到两个链表长度差的位置，然后两个链表的指针一起向后遍历，进行匹配。

/** * 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) { let tempA = headA; let tempB = headB; while (tempA != null && tempB != null) { tempA = tempA.next; tempB = tempB.next; } if (tempA != null) { while (tempA != null) { tempA = tempA.next; headA = headA.next; } } if (tempB != null) { while (tempB != null) { tempB = tempB.next; headB = headB.next; } } while (headA != null && headB != null) { if (headA == headB) { return headA; } headA = headA.next; headB = headB.next; } return null; };

设两条链表长度分别为 m，n：

时间复杂度：O(m+n+max(m,n))；

空间复杂度：O(1)；