题目描述:输入两个链表,找出它们的第一个公共结点。

Solutions

第一反映是遍历一遍两个链表就可以了……

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 is None or pHead2 is None:
            return None
        ll_dict = {}
        p1 = pHead1
        while p1 is not None:
            ll_dict[p1] = 1
            p1 = p1.next
        p2 = pHead2
        while p2 is not None:
            if p2 in ll_dict:
                return p2
            p2 = p2.next
        return None

<p align=center> </p>

第二种方法是分析这种有公共结点的两个链表的形式,可以看出,从第一个公共结点开始后面的都是公共结点,那么我们从最后一个结点往前遍历到最后一个公共结点,即是原来顺序上的第一个公共结点,也就是图中从 7 遍历到 6。但是这里是单向链表不能往前遍历,于是我们想到这种访问顺序是栈的形式,那么同样遍历一遍两个链表利用栈存储,然后按照上面的思路找。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 is None or pHead2 is None:
            return None
        s1 = []
        s2 = []
        p1 = pHead1
        while p1 is not None:
            s1.append(p1)
            p1 = p1.next
        p2 = pHead2
        while p2 is not None:
            s2.append(p2)
            p2 = p2.next
        res = None
        while len(s1) > 0 and len(s2) > 0:
            top1 = s1.pop()
            top2 = s2.pop()
            if top1 == top2:
                res = top1
            else:
                return res
        return None

以上实现没有 AC,尚还没有找到问题所在。

第三种解法是先遍历得到两个链表的长度,然后然后在长的链表上先走对应的步骤就好了。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def length(self, pHead):
        count = 0
        p = pHead
        while p is not None:
            count += 1
            p = p.next
        return count
    
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 is None or pHead2 is None:
            return None
        count1 = self.length(pHead1)
        count2 = self.length(pHead2)
        if count1 > count2:
            max_p, min_p = pHead1, pHead2
            over_count = count1 - count2
        else:
            max_p, min_p = pHead2, pHead1
            over_count = count2 - count1
        for i in range(over_count):
            max_p = max_p.next
        while max_p is not None and min_p is not None:
            if max_p == min_p:
                return max_p
            else:
                max_p = max_p.next
                min_p = min_p.next
        return None
# 运行时间:44ms
# 占用内存:5756k

References

  1. 037. 两个链表的第一个公共结点