两个链表的第一个公共结点

发表于 | 分类于 | 次

###题目

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

解题思路

先分别遍历两个链表并记录长度并记录。然后长的链表先走K步后，两个指针一起遍历，如果第一次出现两个指针相同，则该结点为第一个公共结点。

代码实现

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
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, p1, p2):
        # 较长的链表是快指针
        step = 0
        slow = None
        fast = None
        c1 = 0
        c2 = 0
        t1 = p1
        t2 = p2
        while t1 is not None:
            t1 = t1.next
            c1 = c1 + 1
        while t2 is not None:
            t2 = t2.next
            c2 = c2 + 1
        if c1 > c2:
            step = c1 - c2
            slow = p1
            fast = p2
        else:
            step = c2 - c1
            slow = p2
            fast = p1
        for i in range(0, step):
            slow = slow.next
        while True:
            if slow == fast:
                return slow
            else:
                slow = slow.next
                fast = fast.next