[剑指Offer]两个链表的第一个公共结点

题目描述

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

解题思路

1. 方法一：得到两个链表的长度，然后让长的链表先走长度差步，再同时走，遇到相同的结点即为第一个公共结点。
2. 方法二：两个链表同时走，将走过的记录下来，并同时判断当前结点是否在另一个链表的记录中，一方走完时，公共结点肯定在另一个链表剩下的部分。

代码

Python(2.7.3)

方法一

# -*- 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
        c1, c2 = 0, 0
        cur1, cur2 = pHead1, pHead2
        while cur1 is not None:
            c1 += 1
            cur1 = cur1.next
        while cur2 is not None:
            c2 += 1
            cur2 = cur2.next
        if c1 > c2:
            while c1 - c2 > 0:
                pHead1 = pHead1.next
                c1 -= 1
        else:
            while c2 - c1 > 0:
                pHead2 = pHead2.next
                c2 -= 1
        while pHead1 != pHead2:
            pHead1 = pHead1.next
            pHead2 = pHead2.next
        return pHead1

运行时间：25ms
占用内存：5728k

方法二

# -*- 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
        nodes1 = []
        nodes2 = []
        node1 = pHead1
        node2 = pHead2
        while node1 is not None and node2 is not None:
            if node1 == node2 or node1 in nodes2:
                return node1
            if node2 in nodes1:
                return node2
            nodes1.append(node1)
            nodes2.append(node2)
            node1 = node1.next
            node2 = node2.next
        if node1 is None:
            while node2 is not None and node2 not in nodes1:
                node2 = node2.next
            return node2
        if node2 is None:
            while node1 is not None and node1 not in nodes2:
                node1 = node1.next
            return node1

运行时间：27ms
占用内存：5728k