一、题目

剑指 Offer 52. 两个链表的第一个公共节点

题目描述

输入两个链表，找出它们的第一个公共节点。

示例1：

1
2
输入:  A=[4,1,8,4,5]  B=[5,0,1,8,4,5]
输出: 8

示例2：

1
2
输入:  A=[4,1,8]  B=[5,0,1]
输出: NULL

二、分析

1.方法1:消除差距法

  1. 两个链表相交之后，后面都是一样的，需要找第一个公共节点。
  2. 但是他们的第一个公共节点在哪儿呢。我们通过两个链表的长度之差，定位到长链表的遍历起始地方。
  3. 此举消除了起始位置差，保证了两个链表同时遍历后一定能同时到达第一个公共节点。

在这里插入图片描述

2.方法2：浪漫相遇法

  1. 该方法实质上也是一种消除差距的方法。方法1消除差距是利用长链表遍历的时候先走几步（先出发），直到达到长，短链表遍历能够同步。
  2. 浪漫相遇法两个指针遍历同时出发，都走长短链表之和的路程。虽然前面的路程不同，但是因为有公共节点。后面一截路程一定相同，也就一定会相遇。
  3. 如下图第一个相遇的节点就是所求结果

在这里插入图片描述

三、代码

1.消除差距法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
'''
题目：剑指 Offer 52. 两个链表的第一个公共节点
描述：
方法：消除差距法：
    两个链表相交之后，后面都是一样的，需要找第一个公共节点。
    但是他们的第一个公共节点在哪儿呢。我们通过两个链表的长度之差，定位到长链表的遍历起始地方。
    此举保证了两个链表遍历后一定能同时到达第一个公共节点。
    消除差距是利用长链表遍历的时候先走几步（先出发），直到达到长，短链表遍历能够同步。
复杂度分析：时间O(m+n)：求长度O(m+n) 遍历找公共节点：O(m+n)
            空间O(1)： i，pA,PB
坑：
'''

@staticmethod
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB: return None
    pA, pB = headA, headB
    lenA = lenB = 0  # 两个链表长度
    # 求链表长度
    while pA:
        lenA += 1
        pA = pA.next
    while pB:
        lenB += 1
        pB = pB.next
    # 消除差距长链表遍历的时候先走几步（先出发）
    if lenB >= lenA:
        for i in range(lenB - lenA):  # 通过先出发将差距弥补
            headB = headB.next  # 当前节点
    else:
        for i in range(lenA - lenB):
            headA = headA.next

    while headA and headB:
        if headA is headB:  # 同步出发，相等就是相遇的第一个节点
            return headA
        headA, headB = headA.next, headB.next
    return None # 没有相遇

2.浪漫相遇法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
'''
    题目：剑指 Offer 52. 两个链表的第一个公共节点
    描述：
    方法：浪漫相遇法，为了消除两个的长度差，遍历的时候对两个链路总和进行遍历。只是起点不同，他们总会在第一个节点相遇
    复杂度分析：时间O(m+n)：
                空间O(1)： i，pA,PB
    坑：
'''

    @staticmethod
    def getIntersectionNodeA(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB: return None
        flagA = flagB = False
        pA, pB = headA, headB

        while pA != pB:
            if (flagA and not pA.next) or (flagB and not pB.next): return None
            if pA.next is None:
                pA = headB
                flagA = True
            else:
                pA = pA.next
            if pB.next is None:
                pB = headA
                flagB = True
            else:
                pB = pB.next

        return pA

3.浪漫相遇法优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
题目：剑指 Offer 52. 两个链表的第一个公共节点
描述：
方法：题解，上面方法的优化。在遍历的时候要遍历最后一个节点之后的空节点。这样会使两个链表即使
    没有公共节点，也会在在该节点相遇。就不用单独考虑特殊情况啦
复杂度分析：时间O(m+n)：
            空间O(1)： pA,PB
坑：
'''

@staticmethod
def getIntersectionNodeAA(self, headA: ListNode, headB: ListNode) -> ListNode:
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

4.set集合存储节点，判断重复（补充）

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
'''
题目：剑指 Offer 52. 两个链表的第一个公共节点
描述：
方法：利用set存储一条链表，然后遍历另一条链表，如果发现set中有重复的，那么就是第一个交点
        没有重复的返回None
复杂度分析：时间O(m+n)：遍历两个链表
            空间O(m)： 辅助空间set集合
'''

@staticmethod
def getIntersectionNodeB(self, headA: ListNode, headB: ListNode) -> ListNode:
    pA, pB = headA, headB
    container = set()
    while pA:
        container.add(pA)
        pA = pA.next
    while pB:
        if container.__contains__(pB): return pB
        pB = pB.next
    return None

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* 题目：剑指 Offer 52. 两个链表的第一个公共节点
* 描述：输入两个链表，找出它们的第一个公共节点。
* 实现:
*/
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
	ListNode* p1 = headA;
	ListNode* p2 = headB;
	set<ListNode*> myset;
	while (p1) {
		myset.emplace(p1);
		p1 = p1->next;
	}
	while (p2) {
		if (myset.count(p2)) return p2;
		p2 = p2->next;
	}
	return nullptr;

}

四、总结

此题是双指针的典型题。链表问题要想到用双指针。