剑指36-两个链表的第一个公共结点

Posted on | In |

题目描述

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

找出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
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        p1, p2 = pHead1, pHead2
        len1, len2 = 0, 0
        while p1:
            len1 += 1
            p1 = p1.next
        while p2:
            len2 += 1
            p2 = p2.next
            
        if len1 < len2:
            p1, p2 = pHead2, pHead1
            len1, len2 = len2, len1
        else:
            p1, p2 = pHead1, pHead2
        while len1 > len2:
            len1 -= 1
            p1 = p1.next

        while p1 and p2 and p1 != p2:
            p1 = p1.next
            p2 = p2.next
            
        return p1